05 August 2008
两个 m x n 的二进制矩阵 grid1 和 grid2 ，它们只包含 0 （表示水域）和 1 （表示陆地）。一个 岛屿 是由 四个方向 （水平或者竖直）上相邻的 1 组成的区域。任何矩阵以外的区域都视为水域。
如果 grid2 的一个岛屿，被 grid1 的一个岛屿 完全 包含，也就是说 grid2 中该岛屿的每一个格子都被 grid1 中同一个岛屿完全包含，那么我们称 grid2 中的这个岛屿为 子岛屿 。
返回 grid2 中 子岛屿 的 数目 。
也就是检查grid2中的坐标是否被grid1中的坐标包含覆盖
BFS
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
class Solution {
public int countSubIslands(int[][] grid1, int[][] grid2) {
int rows = grid1.length;
int cols = grid1[0].length;
int res = 0;
//遍历每个位置
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
//如果这个位置为1，并且dfs返回的是true,res++
if (grid2[i][j] == 1 && dfs(grid1, grid2, i, j)) {
res++;
}
}
}
return res;
}
public boolean dfs(int[][] grid1, int[][] grid2, int i, int j) {
//越界或者grid2[i][j] == 0,说明已经到了岛屿外，不需要考虑直接返回true;
if (!inArea(grid1, i, j) || grid2[i][j] == 0) {
return true;
}
//因为grid2[i][j] == 0在上面的条件中已经返回了，所以这里grid2[i][j] == 1
//如果grid1[i][j] == 0说明grid1并没有将grid2包含，返回false。
if (grid1[i][j] == 0) {
return false;
}
//将访问过的置0
grid2[i][j] = 0;
//这里只能用&，因为&&会导致搜索不全
return dfs(grid1, grid2, i + 1, j) & dfs(grid1, grid2, i - 1, j)
& dfs(grid1, grid2, i, j + 1) & dfs(grid1, grid2, i, j - 1);
}
public boolean inArea(int[][] grid, int i, int j) {
return i >= 0 && j >= 0 && i < grid.length && j < grid[0].length;
}
}