Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/711.html
711. Number of Distinct Islands II
Level
Hard
Description
Given a non-empty 2D array grid of 0’s and 1’s, an island is a group of 1’s (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.
Count the number of distinct islands. 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).
Example 1:
11000
10000
00001
00011
Given the above grid map, return 1.
Notice that:
11
1
and
1
11
are considered same island shapes. Because if we make a 180 degrees clockwise rotation on the first island, then two islands will have the same shapes.
Example 2:
11100
10001
01001
01110
Given the above grid map, return 2.
Here are the two distinct islands:
111
1
and
1
1
Notice that:
111
1
and
1
111
are considered same island shapes. Because if we flip the first array in the up/down direction, then they have the same shapes.
Note: The length of each dimension in the given grid does not exceed 50.
Solution
This is a follow-up problem of problem 694. In this problem, rotation and reflection are also considered.
The basic idea is still using breadth first search. However, the way to determine an island’s shape is different.
After rotation, there are at most 4 different states of the shape. After rotation and reflection, there are at most 8 different states of the shape. For each shape met, consider all 8 states, and for each state, use a list to store the positions, where each element in the list is an integer that can uniquely determine a position. Sort the list and convert it into a string. Use the greatest string to represent the state. Use a set to store the strings so that each state corresponds to one element in the set, whether it has been rotated or reflected. Finally, return the set’s size.
-
class Solution { int rows; int columns; public int numDistinctIslands2(int[][] grid) { rows = grid.length; columns = grid[0].length; boolean[][] visited = new boolean[rows][columns]; Set<String> set = new HashSet<String>(); for (int i = 0; i < rows; i++) { for (int j = 0; j < columns; j++) { if (grid[i][j] == 1 && !visited[i][j]) { List<Integer> shapeList = breadthFirstSearch(grid, visited, i, j); if (!shapeList.isEmpty()) { String shapeStr = getShape(shapeList); set.add(shapeStr); } } } } return set.size(); } public List<Integer> breadthFirstSearch(int[][] grid, boolean[][] visited, int row, int column) { List<Integer> shapeList = new ArrayList<Integer>(); int[][] directions = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} }; visited[row][column] = true; Queue<int[]> queue = new LinkedList<int[]>(); queue.offer(new int[]{row, column}); while (!queue.isEmpty()) { int[] cell = queue.poll(); int curRow = cell[0], curColumn = cell[1]; shapeList.add(curRow * columns + curColumn); for (int[] direction : directions) { int newRow = curRow + direction[0], newColumn = curColumn + direction[1]; if (newRow >= 0 && newRow < rows && newColumn >= 0 && newColumn < columns && grid[newRow][newColumn] == 1 && !visited[newRow][newColumn]) { visited[newRow][newColumn] = true; queue.offer(new int[]{newRow, newColumn}); } } } return shapeList; } public String getShape(List<Integer> shapeList) { String shapeStr = ""; int multiple = rows + columns; int[][] signs = { {1, 1}, {-1, 1}, {-1, -1}, {1, -1} }; int size = shapeList.size(); for (int i = 0; i < 4; i++) { int[] rowArray = new int[size]; int[] columnArray = new int[size]; for (int j = 0; j < size; j++) { int position = shapeList.get(j); rowArray[j] = position / columns * signs[i][0]; columnArray[j] = position % columns * signs[i][1]; } int rowMin = rowArray[0], columnMin = columnArray[0]; for (int row : rowArray) rowMin = Math.min(rowMin, row); for (int column : columnArray) columnMin = Math.min(columnMin, column); int[] shapeArray1 = new int[size]; int[] shapeArray2 = new int[size]; for (int j = 0; j < size; j++) { shapeArray1[j] = (rowArray[j] - rowMin) * multiple + (columnArray[j] - columnMin); shapeArray2[j] = (columnArray[j] - columnMin) * multiple + (rowArray[j] - rowMin); } Arrays.sort(shapeArray1); Arrays.sort(shapeArray2); String shapeStr1 = Arrays.toString(shapeArray1); String shapeStr2 = Arrays.toString(shapeArray2); if (shapeStr.compareTo(shapeStr1) < 0) shapeStr = shapeStr1; if (shapeStr.compareTo(shapeStr2) < 0) shapeStr = shapeStr2; } return shapeStr; } } -
class Solution: def numDistinctIslands2(self, grid: List[List[int]]) -> int: def dfs(i, j, shape): shape.append([i, j]) grid[i][j] = 0 for a, b in [[1, 0], [-1, 0], [0, 1], [0, -1]]: x, y = i + a, j + b if 0 <= x < m and 0 <= y < n and grid[x][y] == 1: dfs(x, y, shape) def normalize(shape): shapes = [[] for _ in range(8)] for i, j in shape: shapes[0].append([i, j]) shapes[1].append([i, -j]) shapes[2].append([-i, j]) shapes[3].append([-i, -j]) shapes[4].append([j, i]) shapes[5].append([j, -i]) shapes[6].append([-j, i]) shapes[7].append([-j, -i]) for e in shapes: e.sort() for i in range(len(e) - 1, -1, -1): e[i][0] -= e[0][0] e[i][1] -= e[0][1] shapes.sort() return tuple(tuple(e) for e in shapes[0]) m, n = len(grid), len(grid[0]) s = set() for i in range(m): for j in range(n): if grid[i][j]: shape = [] dfs(i, j, shape) s.add(normalize(shape)) return len(s) -
typedef pair<int, int> PII; class Solution { public: int numDistinctIslands2(vector<vector<int>>& grid) { set<vector<PII>> s; for (int i = 0; i < grid.size(); ++i) { for (int j = 0; j < grid[0].size(); ++j) { if (grid[i][j]) { vector<PII> shape; dfs(i, j, grid, shape); s.insert(normalize(shape)); } } } return s.size(); } vector<PII> normalize(vector<PII>& shape) { vector<vector<PII>> shapes(8); for (auto& e : shape) { int i = e.first, j = e.second; shapes[0].push_back({i, j}); shapes[1].push_back({i, -j}); shapes[2].push_back({-i, j}); shapes[3].push_back({-i, -j}); shapes[4].push_back({j, i}); shapes[5].push_back({j, -i}); shapes[6].push_back({-j, -i}); shapes[7].push_back({-j, i}); } for (auto& e : shapes) { sort(e.begin(), e.end()); for (int k = e.size() - 1; k >= 0; --k) { e[k].first -= e[0].first; e[k].second -= e[0].second; } } sort(shapes.begin(), shapes.end()); return shapes[0]; } void dfs(int i, int j, vector<vector<int>>& grid, vector<PII>& shape) { shape.push_back({i, j}); grid[i][j] = 0; vector<int> dirs = {-1, 0, 1, 0, -1}; for (int k = 0; k < 4; ++k) { int x = i + dirs[k], y = j + dirs[k + 1]; if (x >= 0 && x < grid.size() && y >= 0 && y < grid[0].size() && grid[x][y] == 1) dfs(x, y, grid, shape); } } };