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