在 LeetCode 的网格（Grid）类题目中，DFS（深度优先搜索）和 BFS（广度优先搜索）是最基础也是最重要的两把武器。
很多时候代码写不对，不是因为逻辑没想通，而是死在了细节上：
标记问题：为什么有的题要“恢复现场”（回溯），有的题标记完就不用管了？
分层问题：BFS 为什么要写个
size循环？minutes++到底加在哪里？边界问题：为什么我的 DFS 会死循环（Stack Overflow）？
今天我们通过两道经典题目——200. 岛屿数量和994. 腐烂的橘子，来一次彻底的复盘。
一、 DFS 的主场：岛屿数量 (永久标记法)
1. 核心思路
这道题只关心“连通性”。只要两个 1 是挨着的，它们就属于同一个岛。我们不需要知道岛屿的形状，也不需要知道岛屿的半径，只需要把挨在一起的 1 全部找出来，消耗掉即可。
这非常适合DFS。这就好比哥伦布发现新大陆，只要踩上一块陆地，就派人往四个方向一直跑，把这块大陆的所有角落都插上旗子（标记为 2），防止下次重复发现。
2. 深度解析：永久标记 vs 临时标记
这是很多同学最容易混淆的点：为什么这道题的 DFS 不需要“恢复现场”（回溯）？
我们来对比一下两种标记模式：
模式 A：永久标记（领地占领型）
代表题目：岛屿数量、朋友圈个数。
逻辑：一个格子一旦被访问（被插旗），它就永久属于当前这个连通块了。它不可能既属于岛屿 A，又属于岛屿 B。
操作：
grid[i][j] = '2'。直接改写，不需要在递归结束后改回'1'。回头路：绝对不走。遇到
'2'直接返回，否则会死循环。
模式 B：临时标记（路径探索型）
代表题目：单词搜索 (Word Search)、迷宫所有路径。
逻辑：一个格子虽然在当前这条路径里被占用了，但如果这条路走不通，退回来后，这个格子可能属于另一条正确的路径。
操作：
进门锁门：
board[i][j] = '#'递归探索
出门开锁（恢复现场）：
board[i][j] = original_char
结论：本题属于模式 A。我们是去“消除”岛屿的，不是来找路的，所以不需要恢复现场。
3. 代码实现 (C++)
C++代码实现：
class Solution { // 思路： 遍历这个矩阵如果是1说明是岛屿，就用dfs把这个岛屿都插上旗 // 这样下次遍历到1就一定是新的岛屿 void dfs(vector<vector<char>>& grid, int i, int j) { // Base Case (递归终止条件)： // 1. 越界了 // 2. 不是 '1' (可能是水 '0'，或者是已经插过旗的 '2') // 【关键点】：这里必须判断 grid[i][j] != '1'，否则两个相邻的 1 会互相递归，导致死循环爆栈 if (i >= grid.size() || i < 0 || j >= grid[0].size() || j < 0 || grid[i][j] != '1') { return; } // 标记当前格子，防止走回头路（永久标记） if (grid[i][j] == '1') { grid[i][j] = '2'; } // 向四个方向继续探索（一条路走到黑） dfs(grid, i + 1, j); dfs(grid, i - 1, j); dfs(grid, i, j + 1); dfs(grid, i, j - 1); } public: int numIslands(vector<vector<char>>& grid) { int ans = 0; int m = grid.size(); int n = grid[0].size(); for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { // 只有发现新的陆地 ('1') 时才启动 DFS if (grid[i][j] == '1') { dfs(grid, i, j); ans++; // 岛屿数量 + 1 } } } return ans; } };4. 时空复杂度分析
时间复杂度：O(M * N)。
尽管有递归，但网格中的每个格子最多只会被访问常数次（从 '1' 变为 '2'，之后再遇到就直接返回了）。
空间复杂度：O(M * N)。
在最坏情况下（整个网格全是陆地），DFS 的递归深度可以达到 M * N，需要相应的系统栈空间。
二、 BFS 的主场：腐烂的橘子 (分层遍历)
1. 核心思路
这道题求的是“分钟数”。这在图论里对应的是“层级”或“最小步数”。
如果用 DFS：一个烂橘子会像贪吃蛇一样瞬间穿透整个地图，这不符合“传染同时发生”的物理规律。
必须用BFS：就像水波纹一样，第 1 分钟扩散一圈，第 2 分钟再扩散一圈。
2. 深度解析：为什么是“分层 BFS”？
BFS 有两种写法：
流式 BFS：来一个处理一个，不关心是第几层（适合只求连通性）。
分层 BFS：一次处理一批，明确知道当前是第几层（适合求时间、最短路）。
本题必须用分层 BFS。核心标志就是代码中的int size = q.size();（层序遍历也是）。
这就好比给队列拍了个快照：“现在的队列里有 size 个橘子，它们都是【这一分钟】烂的。我只处理这 size 个。处理过程中新加入队列的，那是【下一分钟】的事，排后面去。”
3. 代码实现 (C++)
C++代码实现：
class Solution { int dx[4] = {0, 1, 0, -1}; int dy[4] = {1, 0, -1, 0}; public: int orangesRotting(vector<vector<int>>& grid) { int m = grid.size(); int n = grid[0].size(); int fresh = 0; queue<pair<int, int>> q; // 1. 初始化：统计新鲜橘子数量，将所有源头（烂橘子）加入队列 for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (grid[i][j] == 1) fresh++; else if (grid[i][j] == 2) q.push({i,j}); } } int minutes = 0; // 特殊情况：如果开始没有新鲜橘子，直接返回 0 if (fresh == 0) return 0; // 2. BFS 核心逻辑 // 【优化点】：只有当 fresh > 0 时才继续循环 // 这样可以避免最后一次队列虽然有烂橘子，但周围没有新鲜橘子时，多算一分钟 while (fresh && !q.empty()) { int size = q.size(); // 【核心】：记录当前层的数量，实现分层 // 把这一层的橘子处理完，才代表过了一分钟 for (int k = 0; k < size; ++k) { // C++17 结构化绑定，直接取出 x, y auto [x, y] = q.front(); q.pop(); for (int i = 0; i < 4; ++i) { int nx = x + dx[i]; int ny = y + dy[i]; // 如果下一个位置没出界， 并且是一个新鲜的橘子， 就进行处理 if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] == 1) { fresh--; grid[nx][ny] = 2; // 标记为烂，避免重复访问 q.push({nx, ny}); // 加入下一层 } } } // 【关键点】：处理完这一层后，时间才加 1 // 放在 for 循环外面！ minutes++; } // 如果 fresh 还没减完，说明有死角，返回 -1 return fresh == 0 ? minutes : -1; } };4. 关键疑问 Q&A
Q: 为什么
minutes++要写在for循环外面？A:因为
for循环里处理的是“同一时刻”发生的事（并发）。假设这一分钟有 5 个橘子同时向外扩散，这 5 次操作都属于同一分钟。只有当这一批都处理完了，时间才会真正流逝。
Q: 为什么循环条件是
while (fresh && !q.empty())？A:这是一个精妙的优化。
通常 BFS 在处理完最后一层烂橘子后，这些橘子会入队。下一轮循环时，它们出队检查周围，发现没东西可传了。虽然没干活，但如果只写
!q.empty()，minutes还是会加 1，导致结果错误（多算一分钟）。加上
fresh判断后，一旦新鲜橘子没了，立马停止循环，时间计算刚刚好。
Q: 这里的
auto [x, y]是什么？A:这是 C++17 的结构化绑定。它等价于
pair<int, int> p = q.front(); int x = p.first; int y = p.second;。虽然老写法完全没问题，但这样写更清晰，像数学公式一样直观。
5. 时空复杂度分析
时间复杂度：O(M * N)。
网格中的每个格子最多入队一次、出队一次。
空间复杂度：O(M * N)。
队列中最多可能存储 M * N 个节点（例如所有橘子都是烂的）。
三、 总结
| 维度 | DFS (岛屿数量) | BFS (腐烂橘子) |
| 思维模式 | 铁头娃：一条路走到黑，不撞南墙不回头 | 水波纹：一层一层向外扩散 |
| 适用场景 | 连通块统计、全排列、路径穷举 | 最短路径、层数统计、时间模拟 |
| 标记方式 | 永久标记 (Grid改值)，不需要恢复现场 | 永久标记 (Grid改值)，利用队列分层 |
| 核心代码 | 递归 (System Stack) | 队列 (Queue) +size循环 |
掌握了这两套模版，LeetCode 上 80% 的网格搜索题你都能拿捏！
