题目地址：

https://www.lintcode.com/problem/number-of-distinct-islands-ii/description

给定一个二维$0-1$矩阵，$1$代表陆地，$0$代表水。问其中有多少个不同的岛屿。一个岛屿就是一个$1$连通块。两个岛屿不同的含义是，其中一个岛屿经过若干次以下操作，逆时针旋转$0°,90°,180°,270°$、沿着水平方向翻转、沿着竖直方向翻转，所得到的每一个图形都与另一个岛屿不同（这里的不同的意思是平移后无法重合）。

思路是DFS + 序列化。上述变换可以由一个二面体群$D_8$来表示，该二面体群包含一个$4$阶循环子群$C_4$，其生成元为逆时针旋转$90°$的操作，记为$\sigma$，同时$D_8$还含一个元素，是沿着竖直方向翻转，记为$\tau$。由二面体群的性质，任意操作都可以表为${\sigma }^k{\tau }^h$，其中$k=0,1,2,3$，$h=0,1$，即同一个岛屿最多可以变出$8$个不同的岛屿出来。问题的关键在于如何判断两个岛屿是相同还是不同的。先通过DFS得到一个$1$连通块，也就是$1$个岛屿，岛屿以Pair对象的list来表示，即每个$1$的坐标包装成Pair对象，然后所有的$1$放进一个list里。接着，我们将这个岛屿做各种变换，关于水平方向、竖直方向翻转以及旋转$180°$，本质上就是将$x$和$y$坐标去乘以$(1,1),(1,-1),(-1,1),(-1,-1)$这样。而旋转$90°$后再沿着竖直方向翻转，等价于$x$坐标和$y$坐标对换（即二面体群里$h$取$1$的情形），对换之后又可以进行乘以$(1,1),(1,-1),(-1,1),(-1,-1)$的操作。这样一共能得到$8$个岛屿。我们希望将这$8$个岛屿选一个代表元，并对其进行序列化，这样下次遇到另一个岛屿的时候，如果两个岛屿的代表元相等，就知道这两个岛屿相等了。 先将岛屿中的Pair进行排序，比如先按照$x$坐标排序，接着再按$y$坐标排序，最后再取排序后排第一的点，以该点为原点，将整个岛屿做平移（等价于所有的点的坐标都去减第一的点的坐标），这样这个岛屿的”平移代表元”就得到了（这里的“平移代表元”的意思是，两个岛屿如果都进行上面的操作，最后得到的Pair序列是一样的，那么这两个岛屿一定能互相平移得到），再将其序列化，加入一个列表。将做各种操作得到的$8$个岛屿都进行上述操作，然后序列化加入一个列表，之后排序后取字典序最小的，作为该岛屿的形状的代表。只要得到所有$1$连通块的形状，再去个重就知道一共有多少个不同岛屿了。代码如下：

import java.util.ArrayList; import java.util.HashSet; import java.util.List; import java.util.Set; public class Solution { class Pair { int x, y; public Pair(int x, int y) { this.x = x; this.y = y; } } /** * @param grid: the 2D grid * @return: the number of distinct islands */ public int numDistinctIslands2(int[][] grid) { // write your code here if (grid == null || grid.length == 0 || grid[0].length == 0) { return 0; } Set<String> set = new HashSet<>(); for (int i = 0; i < grid.length; i++) { for (int j = 0; j < grid[0].length; j++) { if (grid[i][j] == 1) { List<Pair> island = new ArrayList<>(); // 得到当前的1连通块所代表的岛屿，然后得到其代表元，再进行序列化后加入set dfs(i, j, grid, island); set.add(getUniqueIsland(island)); } } } return set.size(); } private String getUniqueIsland(List<Pair> island) { List<String> islands = new ArrayList<>(); int[][] tran = {{1, 1}, {1, -1}, {-1, 1}, {-1, -1}}; // 先得到8个岛的平移代表元的序列化 for (int i = 0; i < 4; i++) { List<Pair> island1 = new ArrayList<>(), island2 = new ArrayList<>(); for (Pair pair : island) { island1.add(new Pair(tran[i][0] * pair.x, tran[i][1] * pair.y)); island2.add(new Pair(tran[i][0] * pair.y, tran[i][1] * pair.x)); } islands.add(islandToString(island1)); islands.add(islandToString(island2)); } // 再取序列化后字典序最小的作为形状的代表 islands.sort(String::compareTo); return islands.get(0); } private String islandToString(List<Pair> island) { island.sort((a, b) -> { if (a.x != b.x) { return Integer.compare(a.x, b.x); } else { return Integer.compare(a.y, b.y); } }); StringBuilder sb = new StringBuilder(); // 取出第一个点，然后做平移 int origX = island.get(0).x, origY = island.get(0).y; for (Pair pair : island) { sb.append(pair.x - origX).append(' ').append(pair.y - origY).append(' '); } return sb.toString(); } private void dfs(int x, int y, int[][] grid, List<Pair> island) { island.add(new Pair(x, y)); // 标记为已经访问过 grid[x][y] = 0; int[] d = {1, 0, -1, 0, 1}; for (int i = 0; i < 4; i++) { int nextX = x + d[i], nextY = y + d[i + 1]; if (0 <= nextX && nextX < grid.length && 0 <= nextY && nextY < grid[0].length && grid[nextX][nextY] == 1) { dfs(nextX, nextY, grid, island); } } } }

时间复杂度$O(\sum c_i\log c_i)$，这里$c_i$是$1$连通块的$1$的个数，空间$O(\sum c_i)$。