[LeetCode]Number of Distinct Islands II

这道题的关键点就是，我们如何把一个岛的形状和和其对应的所有旋转/镜像的集合表示出来。如果我们只考虑岛当前的形状，不考虑之后的旋转/镜像的操作的话，我们可以定一个基准点，比如行数最小的点(break tie by min column)，然后把剩余的点分别按照行和列距离基准点的距离sort，这样我们可以得到对应当前形状的与岛位置无关的一个唯一的表达式(1)，我们再把这个点的序列转化成string这种好比较的类型即可。
另外这道题在表述上有些问题，题目中的原话是：

• An island is considered to be the same as another if they have the same shape, or have the same shape after rotation (90, 180, or 270 degrees only) or reflection (left/right direction or up/down direction).

但事实上，这里的rotation or reflection应该改为rotation and reflection，也就是说我们不是只进行旋转或者镜像，我们可以把两者结合起来，比如先旋转再翻转也是可以的。我们下面进行详细的分析，如果我们只进行旋转或者镜像，对于点(x, y)，基准点按照上面的方法所定，其可以映射为：

1. (x, y)，最开始的状态
2. (y, -x)，顺时针旋转90度
3. (-x, -y)，顺时针旋转180度
4. (-y, x)，顺时针旋转270度
5. (-x, y)，镜像到左半边，镜像到右半边是相同的
6. (x, -y)，镜像到下半边，同镜像到上半边

这里我们看到映射只有六种，但是官方给出来的映射却有八种，其中有两种是需要旋转和镜像的结合才能达到：

1. (y, x)，顺时针旋转90度加竖直方向镜像
2. (-y, -x)，顺时针旋转270加水平方向镜像

以上八种可能就是所有旋转/镜像能达到的可能，为了便于比较，我们取lexicographical order最小的按照表达式(1)的规则所生产的表达式当做这个集合的key。对于所有的岛，我们求出对应的key，然后看有多少不同的即可。时间复杂度O(k * log m)，k为岛的数量，m为岛的平均点数。代码如下：