1 题目200. 岛屿数量给你一个由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提示m grid.lengthn grid[i].length1 m, n 300grid[i][j]的值为0或12 代码实现cclass Solution { public: int numIslands(vectorvectorchar grid) { int ans 0 ; int m grid.size(); if (m 0 ) return 0 ; int n grid[0].size(); for (int i 0 ; i m ; i ){ for (int j 0 ; j n ; j ){ if (grid[i][j] 1){ ans ; dfs (grid , i , j ); } } } return ans ; } void dfs (vectorvectorchar grid , int x , int y ){ int m grid.size(); int n grid[0].size(); if (x 0 || x m || y 0 || y n || grid[x][y] ! 1){ return ; } grid[x][y] 0; dfs (grid,x -1 , y ); dfs (grid,x 1 , y ); dfs (grid,x , y - 1 ); dfs (grid,x , y 1 ); } };javaclass Solution { public int numIslands(char[][] grid) { int ans 0; int m grid.length; if (m 0) return 0; int n grid[0].length; for (int i 0; i m; i) { for (int j 0; j n; j) { if (grid[i][j] 1) { ans; dfs(grid, i, j); } } } return ans; } // DFS把连通陆地全部置为0 private void dfs(char[][] grid, int x, int y) { int m grid.length; int n grid[0].length; // 越界 或者 当前不是陆地直接返回 if (x 0 || x m || y 0 || y n || grid[x][y] ! 1) { return; } // 标记为已访问淹成水 grid[x][y] 0; // 上下左右四个方向 dfs(grid, x - 1, y); dfs(grid, x 1, y); dfs(grid, x, y - 1); dfs(grid, x, y 1); } }思考dfs 或者 bfs ,但是具体怎么写一点思路都没。。。题解核心规则1 陆地0 水上下左右相邻陆地属于同一个岛屿遇到一块陆地岛屿数量 1然后把这块连通的所有陆地全部标记成水避免重复统计两种主流方案DFS深度优先搜索、BFS广度优先搜索。 原理一致发现陆地 → 淹掉整片连通陆地。为什么要 “淹陆地” 不能重复计数。如果不修改网格遍历到同一个岛屿别的位置时会再次当成新岛屿。 原地修改网格不需要额外 visited 数组节省空间。方法一DFS递归版最容易理解流程双重循环遍历网格每一个位置grid[i][j]如果当前是1岛屿总数ans调用 DFS把所有相连的陆地全部置为0DFS 逻辑越界直接返回当前不是陆地1直接返回将当前陆地改成水grid[x][y] 0递归搜索 上、下、左、右四个方向C#include vector using namespace std; class Solution { public: int numIslands(vectorvectorchar grid) { int ans 0; int m grid.size(); if (m 0) return 0; int n grid[0].size(); // 遍历每一个格子 for (int i 0; i m; i) { for (int j 0; j n; j) { if (grid[i][j] 1) { ans; dfs(grid, i, j); } } } return ans; } // DFS把(i,j)相连所有陆地淹成水 void dfs(vectorvectorchar grid, int x, int y) { int m grid.size(); int n grid[0].size(); // 边界判断超出范围或者当前是水直接return if (x 0 || x m || y 0 || y n || grid[x][y] ! 1) { return; } // 当前陆地标记为水 grid[x][y] 0; // 四个方向递归 dfs(grid, x - 1, y); // 上 dfs(grid, x 1, y); // 下 dfs(grid, x, y - 1); // 左 dfs(grid, x, y 1); // 右 } };易错点提醒grid元素是char 1/0不是数字1/0不要写错先判断越界再访问grid[x][y]否则数组越界报错递归深度风险 题目最大网格 300*30090000极端情况全是陆地递归深度 90000会栈溢出这时推荐 BFS 或者迭代版 DFS方法二BFS 队列实现不会栈溢出推荐面试备选思路 找到陆地后把坐标放入队列不断取出队首四个方向查找陆地找到就标记为水并且入队。C#include vector #include queue using namespace std; class Solution { public: int numIslands(vectorvectorchar grid) { int ans 0; int m grid.size(); if (m 0) return 0; int n grid[0].size(); // 四个方向偏移量 int dirs[4][2] {{-1,0}, {1,0}, {0,-1}, {0,1}}; for (int i 0; i m; i) { for (int j 0; j n; j) { if (grid[i][j] 1) { ans; queuepairint, int q; q.push({i, j}); grid[i][j] 0; // 入队立刻标记防止重复入队 while (!q.empty()) { auto [x, y] q.front(); q.pop(); // 遍历四个方向 for (auto d : dirs) { int nx x d[0]; int ny y d[1]; if (nx 0 nx m ny 0 ny n grid[nx][ny] 1) { grid[nx][ny] 0; q.push({nx, ny}); } } } } } } return ans; } };C17 支持auto [x,y]如果编译器不支持替换成int x q.front().first; int y q.front().second; q.pop();做题步骤总结遇到网格类岛屿题通用模板两层循环遍历每个单元格遇到未访问陆地岛屿计数 1DFS/BFS清除整片连通陆地标记为水四个方向固定偏移量{{-1,0},{1,0},{0,-1},{0,1}}复杂度分析设网格行数 m列数 n时间复杂度O(mn)每个格子最多访问一次空间复杂度DFS 最坏 O(mn)全陆地递归栈BFS 最坏 O(min(m,n))3 题目994. 腐烂的橘子在给定的m x n网格grid中每个单元格可以有以下三个值之一值0代表空单元格值1代表新鲜橘子值2代表腐烂的橘子。每分钟腐烂的橘子周围 4 个方向上相邻的新鲜橘子都会腐烂。返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能返回-1。示例 1输入grid [[2,1,1],[1,1,0],[0,1,1]]输出4示例 2输入grid [[2,1,1],[0,1,1],[1,0,1]]输出-1解释左下角的橘子第 2 行 第 0 列永远不会腐烂因为腐烂只会发生在 4 个方向上。示例 3输入grid [[0,2]]输出0解释因为 0 分钟时已经没有新鲜橘子了所以答案就是 0 。提示m grid.lengthn grid[i].length1 m, n 10grid[i][j]仅为0、1或24 代码实现cclass Solution { public: int orangesRotting(vectorvectorint grid) { int m grid.size(); int n grid[0].size(); queuepairint ,int q ; int fresh 0 ; vectorvectorint dirs {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; for (int i 0 ; i m ; i ){ for (int j 0 ; j n ; j){ if (grid[i][j] 2 ){ q.push({i , j}); }else if (grid[i][j] 1){ fresh ; } } } if (fresh 0 ) return 0 ; int time -1 ; while (!q.empty()){ int sz q.size(); for (int k 0 ; k sz ; k){ auto cur q.front(); q.pop(); int x cur.first ; int y cur.second ; for (auto d : dirs){ int nx x d[0]; int ny y d[1]; if (nx 0 nx m ny 0 ny n grid[nx][ny] 1){ grid[nx][ny] 2 ; fresh -- ; q.push({nx, ny}); } } } time ; } if (fresh 0 ) return -1 ; return time ; } };javaimport java.util.LinkedList; import java.util.Queue; class Solution { public int orangesRotting(int[][] grid) { int m grid.length; int n grid[0].length; Queueint[] queue new LinkedList(); int fresh 0; // 上下左右四个方向 int[][] dirs {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 初始化装入所有腐烂橘子统计新鲜橘子数量 for (int i 0; i m; i) { for (int j 0; j n; j) { if (grid[i][j] 2) { queue.offer(new int[]{i, j}); } else if (grid[i][j] 1) { fresh; } } } // 没有新鲜橘子直接返回0 if (fresh 0) { return 0; } // 核心time初始值 -1 int time -1; while (!queue.isEmpty()) { int size queue.size(); // 处理当前同一时间所有腐烂橘子 for (int k 0; k size; k) { int[] cur queue.poll(); int x cur[0]; int y cur[1]; for (int[] d : dirs) { int nx x d[0]; int ny y d[1]; // 边界合法 是新鲜橘子 if (nx 0 nx m ny 0 ny n grid[nx][ny] 1) { grid[nx][ny] 2; fresh--; queue.offer(new int[]{nx, ny}); } } } time; } // 还有新鲜橘子无法腐烂返回-1否则返回时间 return fresh 0 ? -1 : time; } }思考首先要自己做看起来只能bfs因为腐烂是同步扩散的。题解这道题不能用 DFS要用BFS广度优先搜索原因 腐烂是同步扩散每一分钟所有已经腐烂的橘子同时向外感染一层BFS 天然就是一层一层遍历按时间扩散可以直接算出时间。解题步骤先遍历整张网格把所有腐烂橘子 (2)的坐标加入队列BFS 起点统计新鲜橘子 (1)的总数量fresh如果一开始新鲜橘子数量 0直接返回 0开始逐层 BFS每次先获取当前队列大小代表当前这一分钟所有腐烂橘子一次性把这一层全部出队向四个方向感染新鲜橘子感染成功新鲜橘子数量 - 1坐标入队标记为腐烂每完成一层时间timeBFS 结束后判断如果新鲜橘子 0存在无法被感染的橘子 → 返回-1否则返回time关键点必须先记录当前队列 size一层一层处理才能正确计时初始队列存放t0 时刻已经腐烂的橘子。队列里的初始腐烂橘子本身不消耗时间向外扩散一轮才代表经过 1 分钟。如果time 0每轮结束time最后一轮队列里只剩被感染好的橘子四周没有新鲜橘子空循环依然time结果 1 出错。解决方案初始化time -1初始 time-1 每处理完一层不管有没有感染 time推演样例 1一共会执行 4 轮有效扩散最终 time 4 ✅修正后完整 C#include vector #include queue using namespace std; class Solution { public: int orangesRotting(vectorvectorint grid) { int m grid.size(); int n grid[0].size(); queuepairint, int q; int fresh 0; vectorvectorint dirs {{-1,0}, {1,0}, {0,-1}, {0,1}}; // 初始化收集腐烂橘子统计新鲜橘子 for (int i 0; i m; i) { for (int j 0; j n; j) { if (grid[i][j] 2) { q.push({i, j}); } else if (grid[i][j] 1) { fresh; } } } // 没有新鲜橘子直接0 if (fresh 0) return 0; // 关键time初始化为 -1 int time -1; while (!q.empty()) { int sz q.size(); // 处理当前这一分钟所有腐烂橘子 for (int k 0; k sz; k) { auto cur q.front(); q.pop(); int x cur.first; int y cur.second; for (auto d : dirs) { int nx x d[0]; int ny y d[1]; if (nx 0 nx m ny 0 ny n grid[nx][ny] 1) { grid[nx][ny] 2; fresh--; q.push({nx, ny}); } } } // 一层处理完毕时间1 time; } // 还有橘子无法腐烂返回-1 return fresh 0 ? -1 : time; } };样例 [[2,1,1],[1,1,0],[0,1,1]] 推演初始队列(0,0)fresh6time-1第 1 轮 while扩散一圈 → time0第 2 轮 while扩散一圈 → time1第 3 轮 while扩散一圈 → time2第 4 轮 while扩散一圈 → time3第 5 轮 while队列还有最后一批橘子四周无新鲜橘子处理完 → time4队列为空退出循环返回 time4 ✅两种写法对比总结time -1方案简洁、主流题解通用不需要额外hasInfect标记time 0 hasInfect方案可读性更强多加布尔变量判断面试优先记住time -1这个模板腐烂橘子 BFS 专用。边界自测Case3[[0,2]]fresh0直接 return 0不会进入 BFS 逻辑不会出错。Case2存在孤立新鲜橘子BFS 结束后 fresh0返回 - 1。复杂度m 行 n 列时间O(mn)每个格子最多入队一次空间O(mn)最坏所有橘子一开始全腐烂队列存满和岛屿数量对比区分200 岛屿数量连通块计数DFS/BFS 都可以994 腐烂橘子求扩散时间同步分层→ 只能 BFSDFS 无法计算最小时间5 小结题目区分200. 岛屿数量目标统计连通块数量✅ DFS、BFS 均可流程双层遍历网格遇到1→ 岛屿数 1DFS/BFS 将整片连通陆地置0标记已访问特点无需分层、无需计时注意递归 DFS 大数据会栈溢出994. 腐烂的橘子目标多源同步扩散求最短时间✅只能 BFS不能 DFS流程先遍历所有腐烂橘子入队统计新鲜橘子freshfresh 0直接返回 0分层 BFS先记录当前队列大小sztime -1每层处理完time避免结果多 1结束若fresh0返回 - 1特点多源起点、分层模拟时间通用模板要素方向数组上下左右{{-1,0},{1,0},{0,-1},{0,1}}原地修改网格充当访问标记不用额外 visited 数组核心区别岛屿数量遇见起点立刻计数单纯连通块遍历不分层。腐烂橘子预处理所有起点入队必须分层多源扩散计时time-1是关键坑。选型口诀连通块计数 → DFS/BFS 都行最短时间 / 同步扩散 → 只用 BFS高频坑岛屿1是字符不要写成数字 1橘子不能直接用time0循环内先存szq.size()边界判断写在最前面防止数组越界