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
| class Solution {
private final static int[][] DIRECTIONS = new int[][] { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
public int countSubIslands(int[][] grid1, int[][] grid2) {
boolean[][] visited = new boolean[grid2.length][grid2[0].length];
int ans = 0;
for (int i = 0; i < grid2.length; i++) {
for (int j = 0; j < grid2[0].length; j++) {
if (grid2[i][j] == 1 && !visited[i][j]) {
if (dfs(grid1, grid2, i, j, visited)) {
ans += 1;
}
}
}
}
return ans;
}
private boolean dfs(int[][] grid1, int[][] grid2, int row, int col, boolean[][] visited) {
boolean coverAll = true;
if (grid1[row][col] != 1) {
coverAll = false;
}
visited[row][col] = true;
for (int[] direction : DIRECTIONS) {
int newRow = row + direction[0];
int newCol = col + direction[1];
if (!isOutOfBound(grid2, newRow, newCol) && grid2[newRow][newCol] == 1 && !visited[newRow][newCol]) {
if (!dfs(grid1, grid2, newRow, newCol, visited)) {
coverAll = false;
}
}
}
return coverAll;
}
private boolean isOutOfBound(int[][] grid2, int row, int col) {
return row < 0 || col < 0 || row >= grid2.length || col >= grid2[0].length;
}
}
|
常规做法. 就是dfs grid2的时候, 每到一个1处就看grid1对应的位置是不是也是1, 如果是那我们继续, 如果不是, 那就说明grid1不包含这个sub island. 如果dfs完发现每个位置在grid1的对应位置都是1, 那就说明grid1包含这个sub island.
需要注意的是, 我之前写的版本是如果grid1不包含的时候, 我就直接停止dfs返回了, 这是错误的. 因为这样会把grid2的中岛屿给部分侵蚀. 而我们是把岛屿当整个来看的. 比如我到一个位置发现grid1不是1, 我直接停止, grid2中该island剩下还有其他的1没有dfs完. 我们之前来到这个地方的路线经过的1都被标记为已经visited了, 那么这个大island就变成了一个或多个小island. 那么假设我们下面又来到了这其中某个小island, 发现小island中每个位置在grid1中都有对应, 我们会错误地以为这是个sub island, 但是不是的. 这个小island其实是之前上面没有dfs完而产生的小island. 因为我们一边dfs, 一边把land标记为water. 正确地应该是即使发现某个位置是在grid1中不是1, 我们也要dfs完全.
时间复杂度: O(m * n)
空间复杂度: O(m * n)
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
| class Solution {
private final static int[][] DIRECTIONS = new int[][] { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
public int countSubIslands(int[][] grid1, int[][] grid2) {
int ans = 0;
for (int i = 0; i < grid2.length; i++) {
for (int j = 0; j < grid2[0].length; j++) {
if (grid2[i][j] == 1 && dfs(grid1, grid2, i, j)) {
ans += 1;
}
}
}
return ans;
}
private boolean dfs(int[][] grid1, int[][] grid2, int row, int col) {
boolean coverAll = true;
if (grid1[row][col] != 1) {
coverAll = false;
}
grid2[row][col] = 0;
for (int[] direction : DIRECTIONS) {
int newRow = row + direction[0];
int newCol = col + direction[1];
if (!isOutOfBound(grid2, newRow, newCol) && grid2[newRow][newCol] == 1) {
if (!dfs(grid1, grid2, newRow, newCol)) {
coverAll = false;
}
}
}
return coverAll;
}
private boolean isOutOfBound(int[][] grid2, int row, int col) {
return row < 0 || col < 0 || row >= grid2.length || col >= grid2[0].length;
}
}
|
这个是不使用额外的空间, 直接在原grid2上标记. 到一个1后就把这里标记为0.
时间复杂度不变.
空间复杂度是O(1).
s
