# 题目
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和 / 或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
输入：grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
输出：1
输入：grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
输出：3
# DFS
class Solution { | |
public: | |
int count = 0; | |
int numIslands(vector<vector<char>>& grid) { | |
for(int i = 0; i < grid.size(); i++) { | |
for(int j = 0; j < grid[0].size(); j++) { | |
if(grid[i][j] == '1') { | |
count++; | |
dfs(grid, i, j); | |
} | |
} | |
} | |
return count; | |
} | |
void dfs(vector<vector<char>>& grid, int r, int c) { | |
// 判断 base case | |
// 如果坐标（r,c）超出了网格范围，直接返回 | |
if(!isArea(grid, r, c)) return; | |
// 如果这个格子不是岛屿，直接返回 | |
if (grid[r][c] != '1') return; | |
grid[r][c] = 2; // 将格子标记为 2 | |
// 访问上、下、左、右四个相邻结点 | |
dfs(grid, r-1, c); | |
dfs(grid, r+1, c); | |
dfs(grid, r, c-1); | |
dfs(grid, r, c+1); | |
} | |
// 判断坐标（r,c）是否在网格中 | |
bool isArea(vector<vector<char>>& grid, int r, int c) { | |
return (0 <= r && r < grid.size() && 0 <= c && c < grid[0].size()); | |
} | |
}; |
# 网格类 DFS 框架
二叉树的 DFS 遍历有两要素
- 访问邻接节点，对于二叉树而言，邻接节点即左子节点和右子节点两个。
- 判断 base case，一般来说二叉树遍历的 base case 是 rootnull，其有两层含义，一方面，这表示 root 指向的子树为空，不需要再往下遍历了，另一方面，在 rootnull 的时候及时返回，可以让后面的 root.left 和 root.right 操作不会出现空指针异常。
对于网格类 DFS 问题，参考二叉树的 DFS 两要素，写出其两要素
- 上下左右四个邻接节点，如
图1 - 网格 DFS 中的 base case 是什么？网格中不要继续遍历，
grid[r][c]会出现数组越界，即超出了网格范围的格子，这跟二叉树的遍历方法是一样的，先递归调用，发现 root==null 再返回。
如何避免重复的遍历？
与二叉树 DFS 最大不同之处在于，遍历中可能遇到遍历过的节点。
可以标记已经遍历过的节点，我们想在所有值为 1 的格子上 DFS 遍历，每走过一个格子，就把格子值改为 2，当再遇到值为 2 的格子后，就知道已经遍历过了。
void dfs(vector<vector<char>>& grid, int r, int c) { | |
// 判断 base case | |
// 如果坐标（r,c）超出了网格范围，直接返回 | |
if(!isArea(grid, r, c)) return; | |
// 如果这个格子不是岛屿，直接返回 | |
if (grid[r][c] != '1') return; | |
grid[r][c] = 2; // 将格子标记为 2 | |
// 访问上、下、左、右四个相邻结点 | |
dfs(grid, r-1, c); | |
dfs(grid, r+1, c); | |
dfs(grid, r, c-1); | |
dfs(grid, r, c+1); | |
} | |
// 判断坐标（r,c）是否在网格中 | |
bool isArea(vector<vector<char>>& grid, int r, int c) { | |
return (0 <= r && r < grid.size() && 0 <= c && c < grid[0].size()); | |
} |
# 并查集
我们也可以使用并查集代替搜索。
扫描网格，判断其上方以及左方是否为 1 以及自身是否为 1，符合的话并入集合中；
扫描完后，进行第二次合并，查代表元素，即连通块（陆地）的数量。
class Solution { | |
public: | |
int n, m; | |
vector<int> fa; | |
void init(int n) { | |
fa = vector<int>(n); | |
for (int i = 0; i < n; i ++) { | |
fa[i] = i; | |
} | |
} | |
int get(int x) { | |
return x == fa[x] ? x : fa[x] = get(fa[x]); | |
} | |
void merge(int x, int y) { | |
fa[get(x)] = get(y); | |
} | |
int reflect(int x, int y) { | |
return x * m + y; | |
} | |
int numIslands(vector<vector<char>>& grid) { | |
if (grid.empty()) return 0; | |
n = grid.size(), m = grid[0].size(); | |
init(n * m); | |
for (int i = 0 ; i < n; i ++) { | |
for (int j = 0; j < m; j ++) { | |
if (grid[i][j] == '0') continue; | |
if (i && grid[i - 1][j] == '1') merge(reflect(i, j), reflect(i - 1, j)); | |
if (j && grid[i][j - 1] == '1') merge(reflect(i, j), reflect(i, j - 1)); | |
} | |
} | |
int ans = 0; | |
for (int i = 0; i < n; i ++) { | |
for (int j = 0; j < m; j ++) { | |
if (grid[i][j] == '0') continue; | |
else if (fa[reflect(i, j)] == reflect(i, j)) { | |
ans ++; | |
} | |
} | |
} | |
return ans; | |
} | |
}; |
