http://www.cnblogs.com/grandyang/p/7698778.html
X. http://www.cnblogs.com/grandyang/p/7698778.html
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 and only if one island can be translated (and not rotated or reflected) to equal the other.
Example 1:
11000 11000 00011 00011
Given the above grid map, return
1.
Example 2:
11011 10000 00001 11011
Given the above grid map, return
Notice that:
3.Notice that:
11 1
and
1 11
are considered different island shapes, because we do not consider reflection / rotation.
Note: The length of each dimension in the given
grid does not exceed 50.
重点在于如何记录distinct islands shapes。
- 可以用字符串，记录相对坐标串。
- 可以用Integer，记录相对坐标串。
- 可以记录path路径，注意用0记录进出dfs函数的位置用以区分不同形状。
这道题让我们求不同岛屿的个数，是之前那道Number of Islands的拓展，这道题的难点是如何去判断两个岛屿是否是不同的岛屿，首先1的个数肯定是要相同，但是1的个数相同不能保证一定是相同的岛屿，比如例子2中的那两个岛屿的就不相同，就是说两个相同的岛屿通过平移可以完全重合，但是不能旋转。那么我们如何来判断呢，我们发现可以通过相对位置坐标来判断，比如我们使用岛屿的最左上角的1当作基点，那么基点左边的点就是(0,-1)，右边的点就是(0,1), 上边的点就是(-1,0)，下面的点就是(1,0)。那么例子1中的两个岛屿都可以表示为[(0,0), (0,1), (1,0), (1,1)]，点的顺序是基点-右边点-下边点-右下点。通过这样就可以判断两个岛屿是否相同了，下面这种解法我们没有用数组来存，而是encode成了字符串，比如这四个点的数组就存为"0_0_0_1_1_0_1_1_"，然后把字符串存入集合unordered_set中，利用其自动去重复的特性，就可以得到不同的岛屿的数量啦
public int numDistinctIslands(int[][] grid) {
if (grid == null || grid.length < 1 || grid[0].length < 1)
return 0;
int m = grid.length, n = grid[0].length;
Set<String> res = new HashSet<>();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
Set<String> set = new HashSet<>();
if (grid[i][j] == 1) {
dfs(grid, i, j, i, j, set);
res.add(set.toString());
}
}
}
return res.size();
}
public void dfs(int[][] grid, int i, int j, int baseX, int baseY, Set<String> set) {
int m = grid.length, n = grid[0].length;
if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == 0)
return;
set.add((i - baseX) + "_" + (j - baseY));
grid[i][j] = 0;
dfs(grid, i + 1, j, baseX, baseY, set);
dfs(grid, i - 1, j, baseX, baseY, set);
dfs(grid, i, j - 1, baseX, baseY, set);
dfs(grid, i, j + 1, baseX, baseY, set);
}
X. http://www.cnblogs.com/grandyang/p/7698778.html
当然我们也可以不encode字符串，直接将相对坐标存入数组中，然后把整个数组放到集合set中，还是会去掉相同的数组，而且这种解法直接在grid数组上标记访问过的位置，写起来更加简洁了
vector<vector<int>> dirs{{0,-1},{-1,0},{0,1},{1,0}}; int numDistinctIslands(vector<vector<int>>& grid) { int m = grid.size(), n = grid[0].size(); set<vector<pair<int, int>>> res; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (grid[i][j] != 1) continue; vector<pair<int, int>> v; helper(grid, i, j, i, j, v); res.insert(v); } } return res.size(); } void helper(vector<vector<int>>& grid, int x0, int y0, int i, int j, vector<pair<int, int>>& v) { int m = grid.size(), n = grid[0].size(); if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] <= 0) return; grid[i][j] *= -1; v.push_back({i - x0, j - y0}); for (auto dir : dirs) { helper(grid, x0, y0, i + dir[0], j + dir[1], v); } }X. https://segmentfault.com/a/1190000017138588
public int numDistinctIslands(int[][] grid) {
if (grid == null || grid.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) {
StringBuilder sb = new StringBuilder();
dfs(grid, i, j, sb, "start:");
grid[i][j] = 0;
System.out.println(sb.toString());
set.add(sb.toString());
}
}
}
return set.size();
}
private void dfs(int[][] grid, int i, int j, StringBuilder sb, String dir) {
if (i < 0 || i == grid.length || j < 0 || j == grid[0].length || grid[i][j] == 0)
return;
sb.append(dir);
grid[i][j] = 0;
dfs(grid, i - 1, j, sb, "d");
dfs(grid, i + 1, j, sb, "u");
dfs(grid, i, j - 1, sb, "l");
dfs(grid, i, j + 1, sb, "r");
sb.append("#");
}
public int numDistinctIslands(int[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
int m = grid.length, n = grid[0].length;
int[][] directions = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
String[] symbols = { "d", "u", "l", "r" };
Set<String> set = new HashSet<>();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
StringBuilder key = new StringBuilder();
searchDistinctIslandByDFS(i, j, "s", key, directions, symbols, grid);
set.add(key.toString());
}
}
}
return set.size();
}
public void searchDistinctIslandByDFS(int row, int col, String symbol, StringBuilder key, int[][] directions,
String[] symbols, int[][] grid) {
grid[row][col] = 0;
key.append(symbol);
for (int i = 0; i < directions.length; i++) {
int nextRow = row + directions[i][0];
int nextCol = col + directions[i][1];
if (isValid(nextRow, nextCol, grid)) {
searchDistinctIslandByDFS(nextRow, nextCol, symbols[i], key, directions, symbols, grid);
}
}
// back
key.append("b");
}
public boolean isValid(int row, int col, int[][] grid) {
return row >= 0 && row < grid.length && col >= 0 && col < grid[0].length && grid[row][col] == 1;
}
X. Use prime
http://storypku.com/2017/10/leetcode-question-694-number-of-distinct-islands/
http://storypku.com/2017/10/leetcode-question-694-number-of-distinct-islands/
int numDistinctIslands(vector<vector<int>>& grid) {
int m = grid.size();
if (m == 0) return 0;
int n = grid[0].size();
if (n == 0) return 0;
std::unordered_set<int> signatures;
for (int r = 0; r < m; ++r) {
for (int c = 0; c < n; ++c) {
if (grid[r][c]) {
int hash = visit(grid, m, n, r, c);
signatures.insert(hash);
}
}
}
return signatures.size();
}
private:
int visit(vector<vector<int>>& grid, int m, int n, int r, int c) {
bool outOfBound = (r < 0 || r >= m || c < 0 || c >= n);
if (outOfBound || grid[r][c] == 0) return 0;
grid[r][c] = 0;
return 1 + 19 * visit(grid, m, n, r - 1, c)
+ 31 * visit(grid, m, n, r + 1, c)
+ 97 * visit(grid, m, n, r, c - 1)
+ 193 * visit(grid, m, n, r, c + 1);
}
https://www.jianshu.com/p/f722e7d6bb69
X. BFS
http://cqbbshuashua.blogspot.com/2018/05/694-number-of-distinct-islands.html
The tricky part is how to make same shape the same. We store the diff of each point in the shape by x-axial and y axial separately from the start to a list.
11000
11000
00011
00011
The coordinates of last three points of the first shape are: (0, 1), (1,0), (1, 1) the base is (0, 0)
The diff are: 0,1,1,0,1,1
The coordinates of last three points of the second shape are: (2,4), (3,3), (3,4) the base (2,3)
The diff are: 0,1,1,0,1,1
We can draw the conclusion that if the diff lists are the same, then the shape are the same.
ArrayList shape = new ArrayList<Integer>();
public int numDistinctIslands(int[][] grid) {
int n = grid.length;
if(n==0) return 0;
int m = grid[0].length;
Set shapes = new HashSet<ArrayList<Integer>>();
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(grid[i][j]==1){
shape = new ArrayList<Integer>();
markAsZero(grid,i,j,0);
if(!shape.isEmpty()) shapes.add(shape);
}
}
}
return shapes.size();
}
public void markAsZero(int[][] grid, int i, int j, int path){
if(i<0||j<0||i>=grid.length||j>=grid[0].length||grid[i][j]==0) return;
grid[i][j]= 0;
shape.add(path);
markAsZero(grid,i-1,j,1);
markAsZero(grid,i,j-1,2);
markAsZero(grid,i+1,j,3);
markAsZero(grid,i,j+1,4);
shape.add(0);
return;
}X. BFS
http://cqbbshuashua.blogspot.com/2018/05/694-number-of-distinct-islands.html
The tricky part is how to make same shape the same. We store the diff of each point in the shape by x-axial and y axial separately from the start to a list.
11000
11000
00011
00011
The coordinates of last three points of the first shape are: (0, 1), (1,0), (1, 1) the base is (0, 0)
The diff are: 0,1,1,0,1,1
The coordinates of last three points of the second shape are: (2,4), (3,3), (3,4) the base (2,3)
The diff are: 0,1,1,0,1,1
We can draw the conclusion that if the diff lists are the same, then the shape are the same.
public int numDistinctIslands(int[][] grid) { if (grid == null || grid.length == 0 || grid[0].length == 0) return 0; Set<List<Integer>> set = new HashSet<>(); int[][] dirs = new int[][]{{1, 0}, {-1 ,0}, {0, 1}, {0, -1}}; int m = grid.length; int n = grid[0].length; for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) { if (grid[i][j] == 1) { Queue<Integer> queue = new LinkedList<>(); queue.offer(i*n + j); grid[i][j] = -1; List<Integer> list = new ArrayList<>(); while (!queue.isEmpty()) { int cur = queue.poll(); for (int[] dir: dirs) { int newr = cur/n + dir[0]; int newc = cur%n + dir[1]; if (newr >= 0 && newr < m && newc >=0 && newc < n && grid[newr][newc] == 1) { grid[newr][newc] = -1; queue.offer(newr*n + newc); list.add(newr - i); list.add(newc - j); } } } set.add(list); } } return set.size(); }
vector<vector<int>> dirs{{0,-1},{-1,0},{0,1},{1,0}}; int numDistinctIslands(vector<vector<int>>& grid) { int m = grid.size(), n = grid[0].size(); set<vector<pair<int, int>>> res; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (grid[i][j] != 1) continue; vector<pair<int, int>> v; queue<pair<int, int>> q{{{i, j}}}; grid[i][j] *= -1; while (!q.empty()) { auto t = q.front(); q.pop(); for (auto dir : dirs) { int x = t.first + dir[0], y = t.second + dir[1]; if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] <= 0) continue; q.push({x, y}); grid[x][y] *= -1; v.push_back({x - i, y - j}); } } res.insert(v); } } return res.size(); }
