网格图（DFS/BFS/综合应用）
一、网格图DFS
适用于需要计算联通块个数、大小的题目。
部分题目做法不止一种，也可以用BFS或者并查集解决。
二叉树和网格图递归的区别：
| 二叉树 | 网格图 | |
|---|---|---|
| 递归入口 | 根节点 | 网格图的某个格子 |
| 递归方向 | 左子树和右子树 | 一般为左右上下的相邻的格子 |
| 递归边界 | 空节点（或者叶子节点） | 出界、遇到障碍或者已访问 |
200、岛屿数量（20250728）
Details
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
示例 1：
输入：grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
输出：1示例 2：
输入：grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
输出：3这里通过灵神的题解来详细解释一下：把访问过的格子插上旗子🚩（Python/Java/C++/C/Go/JS/Rust）
通过题目我们知道就是求岛屿的数量。
假设你是哥伦布。先从左上角开始，把第一个岛上全部插满🚩，这里用2表示。插满旗子后，把答案（岛屿个数）加一。
⚠️注意：在岛上，你只能左右上下走，不能斜着走。
一个岛屿插满之后，继续遍历，然后去到另外一个岛屿。如果没有1，就表示算法结束了，🚩插满了。
如何实现？
一旦我们发现是1，就从开始，DFS这个岛，每一步可以往左右上下四个方向走，也就是：
这四个格子。
如果出界，或者是水，或者已经插上旗子，就不再继续往下递归。
答疑
1、如何理解递归？
递归的思想是，假设你是一家公司的老板，你不需要亲力亲为，而是拆解问题，交给下属去做。对于这题来说，就是从岛屿的某个位置登陆插旗子，然后一分为四，把探索整个岛屿的任务交给其他人去处理，自己只需要处理好第一步就行。
2、我可以先判断是否等于1，再判断是否出界吗？
不行，因为无法确保i，j是否是合法下标。比如i=-1，获取到就下标越界了，要先保证下标在范围中，再去获取数据元素。
（在获取数组元素的时候，需要确保下标的合法性）
3、我可以把这行代码写在dfs的最后一行吗？
不行，这样会先执行递归，导致反复横跳，无限递归。比如从点到点，在移动到点
4、DFS中能只考虑往右和往下走吗？
不行，比如蚊香型岛屿，在探索的时候必须具备左右上下走的能力。
class Solution {
public int numIslands(char[][] grid) {
int ans = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[i].length; j++) {
if (grid[i][j] == '1') { // 找到了一个新的岛
dfs(grid, i, j); // 把这个岛插满旗子，这样后面遍历到的 '1' 一定是新的岛
// 循环完之后在++
ans++;
}
}
}
return ans;
}
private void dfs(char[][] grid, int i, int j) {
// 递归出口
if (i < 0 || i >= grid.length || j < 0 || j >= grid[i].length || grid[i][j] != '1') {
return;
}
// 不能将这一行写道最后，如果写在最后，会先执行递归，会一直递归
// 比如(0,0) -> (0,1) -> (0,0)
grid[i][j] = '2';
dfs(grid, i, j - 1);
dfs(grid, i, j + 1);
dfs(grid, i - 1, j);
dfs(grid, i + 1, j);
}
}...
695. 岛屿的最大面积（20250728）
认真解决了第一题，这道题就很容易的解决了，就是给dfs加上返回值。
class Solution {
public int maxAreaOfIsland(int[][] grid) {
int mx = 0;
int m = grid.length, n = grid[0].length;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
int ans = dfs(grid, i, j);
mx = Math.max(mx, ans);
}
}
}
return mx;
}
private int dfs(int[][] grid, int i, int j) {
if (i < 0 || i >= grid.length || j < 0 || j >= grid[i].length || grid[i][j] != 1) {
return 0;
}
grid[i][j] = 2;
return 1 + dfs(grid, i, j - 1) + dfs(grid, i, j + 1) + dfs(grid, i - 1, j) + dfs(grid, i + 1, j);
}
}二、网格图 BFS
适用于需要计算最短距离（最短路）的题目。
三、网格图 0-1 BFS
边权只有 0 和 1 的题目，也可以用 BFS 做。
四、网格图 Dijkstra
见 图论题单 中的 Dijkstra。
五、综合应用
思考题 1、对于 m 行 n 列的网格图，BFS 的队列最多消耗多少空间？DFS 的递归栈最多消耗多少空间？ 2、构造一个网格图，让 DFS 的递归深度尽量大。如果起点是 (0,0) 要如何构造？如果起点是 (i,j) 要如何构造？
Changelog
4c155-on