# 711. Number of Distinct Islands II

• Time: $O(mn\log(mn))$
• Space: $O(mn)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 class Solution { public: int numDistinctIslands2(vector>& grid) { const int m = grid.size(); const int n = grid[0].size(); set>> islands; // All different shape islands vector> seen(m, vector(n)); for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) { vector> island; dfs(grid, i, j, seen, island); if (!island.empty()) islands.insert(normalize(island)); } return islands.size(); } private: void dfs(const vector>& grid, int i, int j, vector>& seen, vector>& island) { if (i < 0 || i == grid.size() || j < 0 || j == grid[0].size()) return; if (grid[i][j] == 0 || seen[i][j]) return; seen[i][j] = true; island.emplace_back(i, j); dfs(grid, i + 1, j, seen, island); dfs(grid, i - 1, j, seen, island); dfs(grid, i, j + 1, seen, island); dfs(grid, i, j - 1, seen, island); } vector> normalize(const vector>& island) { // points[i] := 8 different rotations/reflections of island vector>> points(8); for (const auto& [i, j] : island) { points[0].emplace_back(i, j); points[1].emplace_back(i, -j); points[2].emplace_back(-i, j); points[3].emplace_back(-i, -j); points[4].emplace_back(j, i); points[5].emplace_back(j, -i); points[6].emplace_back(-j, i); points[7].emplace_back(-j, -i); } for (vector>& p : points) sort(begin(p), end(p)); // Normalize each p by minus p[1:] w/ p[0] for (vector>& p : points) { for (int i = 1; i < island.size(); ++i) p[i] = {p[i].first - p[0].first, p[i].second - p[0].second}; p[0] = {0, 0}; } sort(begin(points), end(points)); return points[0]; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 class Solution { public int numDistinctIslands2(int[][] grid) { final int m = grid.length; final int n = grid[0].length; Set>> islands = new HashSet<>(); // All different shape islands boolean[][] seen = new boolean[m][n]; for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) { List> island = new ArrayList<>(); dfs(grid, i, j, seen, island); if (!island.isEmpty()) islands.add(normalize(island)); } return islands.size(); } private void dfs(int[][] grid, int i, int j, boolean[][] seen, List> island) { if (i < 0 || i == grid.length || j < 0 || j == grid[0].length) return; if (grid[i][j] == 0 || seen[i][j]) return; seen[i][j] = true; island.add(new Pair<>(i, j)); dfs(grid, i + 1, j, seen, island); dfs(grid, i - 1, j, seen, island); dfs(grid, i, j + 1, seen, island); dfs(grid, i, j - 1, seen, island); } private List> normalize(List> island) { // points[i] := 8 different rotations/reflections of island Pair[][] points = new Pair[8][island.size()]; for (int k = 0; k < island.size(); ++k) { final int i = island.get(k).getKey(); final int j = island.get(k).getValue(); points[0][k] = new Pair<>(i, j); points[1][k] = new Pair<>(i, -j); points[2][k] = new Pair<>(-i, j); points[3][k] = new Pair<>(-i, -j); points[4][k] = new Pair<>(j, i); points[5][k] = new Pair<>(j, -i); points[6][k] = new Pair<>(-j, i); points[7][k] = new Pair<>(-j, -i); } for (Pair[] p : points) Arrays.sort(p, (a, b) -> a.getKey().equals(b.getKey()) ? a.getValue() - b.getValue() : a.getKey() - b.getKey()); // Normalize each p by minus p[1:] w/ p[0] for (Pair[] p : points) { for (int i = 1; i < island.size(); ++i) p[i] = new Pair<>(p[i].getKey() - p[0].getKey(), p[i].getValue() - p[0].getValue()); p[0] = new Pair<>(0, 0); } Arrays.sort(points, new Comparator[]>() { @Override public int compare(Pair[] a, Pair[] b) { for (int i = 0; i < a.length; ++i) { if (a[i].getKey() != b[i].getKey()) return a[i].getKey() - b[i].getKey(); if (a[i].getValue() != b[i].getValue()) return a[i].getValue() - b[i].getValue(); } return 0; } }); return Arrays.asList(points[0]); } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 class Solution: def numDistinctIslands2(self, grid: List[List[int]]) -> int: seen = set() def dfs(i: int, j: int): if i < 0 or i == len(grid) or j < 0 or j == len(grid[0]): return if grid[i][j] == 0 or (i, j) in seen: return seen.add((i, j)) island.append((i, j)) dfs(i + 1, j) dfs(i - 1, j) dfs(i, j + 1) dfs(i, j - 1) def normalize(island: List[tuple]) -> List[tuple]: # points[i] := 8 different rotations/reflections of island points = [[] for _ in range(8)] for i, j in island: points[0].append((i, j)) points[1].append((i, -j)) points[2].append((-i, j)) points[3].append((-i, -j)) points[4].append((j, i)) points[5].append((j, -i)) points[6].append((-j, i)) points[7].append((-j, -i)) points = [sorted(p) for p in points] # Normalize each p by minus p[1:] w/ p[0] for p in points: for i in range(1, len(island)): p[i] = (p[i][0] - p[0][0], p[i][1] - p[0][1]) p[0] = (0, 0) return sorted(points)[0] islands = set() # All different shape islands for i in range(len(grid)): for j in range(len(grid[0])): island = [] dfs(i, j) if island: islands.add(frozenset(normalize(island))) return len(islands)