1. 整体设计与思路拆解1.1 四道题到底在练什么代码随想录算法训练营走到第五十七天图论部分的题目已经不再是单纯的“能不能写出DFS/BFS”而是开始考验“用DFS/BFS解决实际问题”的能力了。今天这四道题——孤岛的总面积、沉没孤岛、水流问题、建造最大岛屿——本质上都是围绕着“网格图上的连通性问题”展开的但每一道题的侧重点又完全不一样。先说孤岛的总面积和沉没孤岛这两道题其实是同一类问题的两个变体都是要求“不接触边界的岛屿”。区别在于一个只需要统计面积另一个需要把孤岛原封不动地“变成水”。水流问题是典型的多源DFS/BFS从四个边界出发反向遍历考察的是能不能把“从边界开始探索”的思路玩明白。建造最大岛屿则是前几道题的综合升级版需要在遍历的基础上引入“岛屿编号”和“面积映射”的概念属于状态记录与合并的范畴。从训练节奏上看这四道题的难度是递进的。前两道题是最经典的“陆地边界判定”问题掌握一套模板就能通吃。第三道题需要转换思维——正向想很难反过来想就通了。第四道题则是前面积累技巧的集大成者需要同时处理好“遍历”“记录”“去重”三件事。1.2 为什么推荐DFS而不是BFS在代码随想录的题解里一直强调能用DFS就用DFS因为代码更短递归的思维更贴近“一块陆地去找另一块陆地”的自然逻辑。BFS当然也能做但对于这类连通块遍历的题目BFS需要自己维护队列、记录每一层代码量会明显增加。我在实际刷题中试过两种写法结论是DFS的代码量大约是BFS的60%到70%而且出错的概率更低。原因很简单DFS的思路是“从当前格子向四个方向递归深入”只需要一个二维visited数组记录走过没有BFS则需要处理队列的入队出队顺序还要小心别把同一个格子重复入队。当然如果题目明确要求“最短路径”或者“逐层扩散”BFS就是唯一选择。但这四道题都只关心“连通块的大小”或者“能不能到达”DFS就足够了。后面我在每道题里都会给出完整代码直接用DFS的写法。注意用DFS处理网格图时递归深度最坏情况下等于网格大小。针对力扣的约束一般不超过2500个格子完全不用担心栈溢出。个人测试下来5000x5000的网格用DFS处理会栈溢出但力扣的常规数据规模远达不到这个级别。2. 核心细节解析与实操要点2.1 网格图DFS的标准模板先复习一下网格图上DFS的四个关键部分因为四道题全部建立在这个模板之上。网格图的每个节点就是格子本身节点之间的“边”就是上下左右四个方向。方向可以用两个数组表示int dir[4][2] {0, 1, 1, 0, -1, 0, 0, -1};其中每个元素代表一个方向的位移{0, 1}是右{1, 0}是下{-1, 0}是上{0, -1}是左。这个方向数组非常常用建议直接记下来省得每次现写。DFS函数的骨架长这样void dfs(vectorvectorint grid, vectorvectorbool visited, int x, int y) { for (int i 0; i 4; i) { int nextx x dir[i][0]; int nexty y dir[i][1]; if (nextx 0 || nextx grid.size() || nexty 0 || nexty grid[0].size()) continue; if (grid[nextx][nexty] 0) continue; if (visited[nextx][nexty]) continue; visited[nextx][nexty] true; dfs(grid, visited, nextx, nexty); } }这个模板有几个容易踩坑的细节。第一边界判断务必要放在最前面否则数组越界直接崩溃第二要把“访问标记”放在递归之前而不是递归之后否则会死循环第三每道题在递归体内需要做的事不同——有的要累加面积有的要修改值但骨架是不变的。2.2 核心算法的思维方式正向思考 vs. 逆向思考这四道题放在一起最大的启发价值在于有一类问题正着想很麻烦但逆向思考就能直接秒杀。孤岛的总面积正着想是“先找到所有岛屿再判断哪些不靠边”。这种做法需要在DFS内部再嵌套一次边界检查复杂度高、容易出错。更优雅的思路是“把所有靠边的陆地全部删掉剩下的陆地就全是孤岛”。具体操作就是先遍历四条边界只要是陆地就触发DFS把这一整块与边界相连的岛屿全部标记为已访问之后再去遍历整个网格遇到“未被访问的陆地”就直接用DFS统计面积。沉没孤岛的逻辑几乎一模一样先处理边界连通块但这里不是标记访问而是把边界连通块先临时标记成另一种值比如-1遍历完边界后把网格中所有仍为1的格子改成0再把所有-1改回1。这样一个原地修改就能完成“沉没孤岛”。水流问题则是逆向思考的经典代表。正着做是要从每个格子出发判断能不能同时到达太平洋和大西洋这个计算成本太高。反过来从太平洋的边界出发所有能走到的地方必然是“能流到太平洋”的格子从大西洋的边界出发同理。两个集合取交集就是答案。这种逆向DFS省去了对每个格子单独做一次搜索的巨大开销。3. 实操过程与核心环节实现3.1 孤岛的总面积题目链接待补充可在代码随想录训练营题目列表中获取或搜索“力扣 孤岛的总面积”。这道题我直接给一个可用版本int n, m; int dir[4][2] {0, 1, 1, 0, -1, 0, 0, -1}; int res 0; void dfs(vectorvectorint grid, vectorvectorbool visited, int x, int y) { res; visited[x][y] true; for (int i 0; i 4; i) { int nextx x dir[i][0]; int nexty y dir[i][1]; if (nextx 0 || nextx n || nexty 0 || nexty m) continue; if (grid[nextx][nexty] 0) continue; if (visited[nextx][nexty]) continue; dfs(grid, visited, nextx, nexty); } } int main() { cin n m; vectorvectorint grid(n, vectorint(m)); for (int i 0; i n; i) for (int j 0; j m; j) cin grid[i][j]; vectorvectorbool visited(n, vectorbool(m, false)); // 去掉所有与边界相连的陆地 for (int i 0; i n; i) { if (grid[i][0] 1 !visited[i][0]) dfs(grid, visited, i, 0); if (grid[i][m - 1] 1 !visited[i][m - 1]) dfs(grid, visited, i, m - 1); } for (int j 0; j m; j) { if (grid[0][j] 1 !visited[0][j]) dfs(grid, visited, 0, j); if (grid[n - 1][j] 1 !visited[n - 1][j]) dfs(grid, visited, n - 1, j); } // 统计剩余陆地的面积即孤岛总面积 res 0; for (int i 0; i n; i) { for (int j 0; j m; j) { if (grid[i][j] 1 !visited[i][j]) { dfs(grid, visited, i, j); } } } cout res endl; return 0; }这里有个细节注意一下第一个dfs的res累加是无效的因为边界连通块不属于孤岛所以我在统计前把res重置为0。这种做法是省写一个cnt参数直接在dfs里更新全局变量逻辑上更简洁。我试过更稳妥的写法是给dfs传一个引用类型的计数器void dfs(..., int count)这样边界遍历和孤岛遍历可以使用完全相同的计数方式只是使用不同的变量接收结果。两个方案都行但个人更喜欢全局变量加重置的做法代码量少。3.2 沉没孤岛沉没孤岛的代码主框架与上一题完全相同唯一的区别在于最后一步修改的是grid本身而不只是维护visited。int n, m; int dir[4][2] {0, 1, 1, 0, -1, 0, 0, -1}; void dfs(vectorvectorint grid, vectorvectorbool visited, int x, int y, int target) { visited[x][y] true; grid[x][y] target; for (int i 0; i 4; i) { int nextx x dir[i][0]; int nexty y dir[i][1]; if (nextx 0 || nextx n || nexty 0 || nexty m) continue; if (grid[nextx][nexty] 0 || grid[nextx][nexty] target) continue; if (visited[nextx][nexty]) continue; dfs(grid, visited, nextx, nexty, target); } } int main() { cin n m; vectorvectorint grid(n, vectorint(m)); for (int i 0; i n; i) for (int j 0; j m; j) cin grid[i][j]; vectorvectorbool visited(n, vectorbool(m, false)); // 先把边界连通块临时标记为-1 for (int i 0; i n; i) { if (grid[i][0] 1 !visited[i][0]) dfs(grid, visited, i, 0, -1); if (grid[i][m - 1] 1 !visited[i][m - 1]) dfs(grid, visited, i, m - 1, -1); } for (int j 0; j m; j) { if (grid[0][j] 1 !visited[0][j]) dfs(grid, visited, 0, j, -1); if (grid[n - 1][j] 1 !visited[n - 1][j]) dfs(grid, visited, n - 1, j, -1); } // 沉没孤岛将所有1变为0孤岛然后恢复-1为1非孤岛 for (int i 0; i n; i) { for (int j 0; j m; j) { if (grid[i][j] -1) grid[i][j] 1; else if (grid[i][j] 1) grid[i][j] 0; } } for (int i 0; i n; i) { for (int j 0; j m; j) { cout grid[i][j] ; } cout endl; } return 0; }这里最关键的技巧就是“引入-1作为中间状态”。如果不引入中间状态直接顺手把边界连通块改成0那后面就没法区分“原本是水的0”和“被改掉的陆地0”了恢复的时候会一头雾水。实际练习时我自己写的第一版就踩了这个坑直接在边界dfs里把grid[i][j]改成0然后遍历时以为剩下1都是孤岛。结果输出一看边界连通块内部的陆地也全变成1了——因为它们被改成的0在第二遍遍历时根本不在“1”的判断条件里孤岛倒是沉没了但非孤岛也毁了。3.3 水流问题水流问题的输入是二维矩阵每个格子的数值代表海拔高度。水只能从高处往低处流允许相等。题目问哪些格子的水既能流到左边界/上边界太平洋又能流到右边界/下边界大西洋。这道题的正向思维是对每个格子做一次DFS看能不能同时到达两个海洋。但这意味着每个格子都要做两次完整搜索效率极低。实际上大多数格子是不满足条件的但在判断之前你并不知道所以所有格子都要搜一遍整体时间复杂度接近O(nm4^(nm))直接爆炸。逆向思维从太平洋的边界左列和上行出发往海拔高或相等的方向反向搜索凡是能到达的格子其水流一定能流到太平洋。这个“反向搜索”的条件和正向搜索一样是matrix[nextx][nexty] matrix[x][y]——即下一格的海拔不低于当前格。同理从大西洋边界右列和下行做同样的操作。两个布尔矩阵分别记录哪些格子能到太平洋、哪些能到大西洋。最后遍历所有格子同时满足两种情况的就是答案。int n, m; int dir[4][2] {0, 1, 1, 0, -1, 0, 0, -1}; void dfs(vectorvectorint matrix, vectorvectorbool ocean, int x, int y) { ocean[x][y] true; for (int i 0; i 4; i) { int nextx x dir[i][0]; int nexty y dir[i][1]; if (nextx 0 || nextx n || nexty 0 || nexty m) continue; if (matrix[nextx][nexty] matrix[x][y] !ocean[nextx][nexty]) { dfs(matrix, ocean, nextx, nexty); } } } int main() { cin n m; vectorvectorint matrix(n, vectorint(m)); for (int i 0; i n; i) for (int j 0; j m; j) cin matrix[i][j]; vectorvectorbool pacific(n, vectorbool(m, false)); vectorvectorbool atlantic(n, vectorbool(m, false)); for (int i 0; i n; i) { dfs(matrix, pacific, i, 0); dfs(matrix, atlantic, i, m - 1); } for (int j 0; j m; j) { dfs(matrix, pacific, 0, j); dfs(matrix, atlantic, n - 1, j); } for (int i 0; i n; i) { for (int j 0; j m; j) { if (pacific[i][j] atlantic[i][j]) { cout i j endl; } } } return 0; }这个解法的正确性我一开始不太确定专门用一个小的例子推过一遍。比如一个3x3矩阵中心格子海拔很高四周很低。正向看水是从中心流向四条边最终能到两个海洋。反向来看从太平洋边界出发往高处爬如果中心足够高两条边界搜索都能到达中心中心就满足条件。非常合理。这里有个小细节海水流向判断是“海拔大于等于”也就是相等高度也能流动。如果理解成“严格大于”那就错了因为题目明确说海拔相同的水也可以流动。这是一个最容易掉进去的坑。3.4 建造最大岛屿这道题是卡哥训练营里的压轴题。题意是给你一个0和1组成的网格0代表海洋1代表陆地你可以把最多一个0变成1求变完之后的“最大岛屿面积”。我第一次做这题时直接想暴力遍历每个0格子把它改成1然后跑一遍DFS算最大连通块。这样做的复杂度是O(K * N * M)K是0的数量。如果网格全是0K接近NM总复杂度是O((NM)^2)数据规模稍微大一点就超时。正确思路是“分析映射”先遍历所有未访问的陆地格子给每个岛屿一个编号islandId同时记录这个岛屿的面积存入一个map键是岛屿编号值是面积。再遍历所有0格子四个方向上找相邻的岛屿编号注意去重因为不同方向可能是同一个岛屿把所有相邻岛屿面积加起来再加上1当前格本身就是把这个格子变成陆地后的新岛屿面积。所有0格子的结果取最大值。这里有两个关键点。第一编号可以直接用下标当编号方便又不重复。第二去重问题非常隐蔽如果一个0格子的上下左右都连着同一个岛屿那四个方向找到的岛屿编号是一样的如果不做去重同一个岛屿的面积会被加多次。我用一个unordered_set来做去重每次遇到0格子就new一个set把四个方向的岛屿编号插入set最后遍历set累加面积。int n, m; int dir[4][2] {0, 1, 1, 0, -1, 0, 0, -1}; int islandCnt 0; unordered_mapint, int islandArea; // key: 岛屿编号, value: 面积 void dfs(vectorvectorint grid, vectorvectorint islandMark, int x, int y, int mark) { islandMark[x][y] mark; islandArea[mark]; for (int i 0; i 4; i) { int nextx x dir[i][0]; int nexty y dir[i][1]; if (nextx 0 || nextx n || nexty 0 || nexty m) continue; if (grid[nextx][nexty] 0) continue; if (islandMark[nextx][nexty] ! 0) continue; dfs(grid, islandMark, nextx, nexty, mark); } } int main() { cin n m; vectorvectorint grid(n, vectorint(m)); vectorvectorint islandMark(n, vectorint(m, 0)); for (int i 0; i n; i) for (int j 0; j m; j) cin grid[i][j]; // 给所有岛屿编号 for (int i 0; i n; i) { for (int j 0; j m; j) { if (grid[i][j] 1 islandMark[i][j] 0) { islandCnt; dfs(grid, islandMark, i, j, islandCnt); } } } int maxArea 0; // 如果全图都是陆地直接输出最大岛屿面积 if (islandCnt 1 islandArea[1] n * m) { cout n * m endl; return 0; } // 遍历所有0格子 for (int i 0; i n; i) { for (int j 0; j m; j) { if (grid[i][j] 0) { unordered_setint neighbors; for (int k 0; k 4; k) { int nextx i dir[k][0]; int nexty j dir[k][1]; if (nextx 0 || nextx n || nexty 0 || nexty m) continue; if (islandMark[nextx][nexty] ! 0) { neighbors.insert(islandMark[nextx][nexty]); } } int total 1; for (int id : neighbors) { total islandArea[id]; } maxArea max(maxArea, total); } } } // 如果全是海洋没有岛屿可合并结果应该是1 cout (maxArea 0 ? 1 : maxArea) endl; return 0; }这里我额外加了一个特判如果整个网格全是1那根本没有0格子可以改最大岛屿面积就是n*m直接输出。这个情况如果你忘记处理代码会走进遍历0格子的循环但循环体一次都不会执行maxArea保持为0最后输出错误。还有一个细节如果全是0没有任何岛屿那最大岛屿面积应该是1把任何一个0变成1孤零零的一块陆地面积就是1。我在代码最后加了maxArea0时输出1的判断防止这种极端情况出错。4. 常见问题与排查技巧实录4.1 边界检查顺序反了这是我刷题时犯过的最蠢的错误先访问grid[nextx][nexty]再做边界判断。如果nextx超出了范围直接数组越界本地运行还能报错提交到OJ上就是莫名其妙的Runtime Error。正确做法永远是先做边界判断再做值判断。4.2 忘记标记访问状态DFS的访问标记非常关键。如果忘记在进入递归前把当前格子标记为已访问会导致两种情况要么死循环A访问BB访问A无限递归要么同一个格子被重复计数统计面积时面积虚高。我自己的经验是把visited[x][y] true放在dfs函数的第一行只要进入函数就立刻标记而不是等往下扩展时才标记。这样更符合直觉也减少“入口没标记”的遗漏。4.3 孤岛判定时把边界遍历的计数混入结果第一道题里如果忘记在统计孤岛面积之前将res重置为0最终结果会把所有边界连通块的面积也加进去。这个错比较隐蔽尤其是测试数据恰好只有孤岛没有边界岛屿时结果碰巧是对的一旦数据里有靠边的岛屿答案就会莫名其妙地偏大。排查时思路很简单每次复用全局变量之前想清楚上一次的值还残留了没有。4.4 水流问题中方向搞反反向dfs时条件是matrix[nextx][nexty] matrix[x][y]即从海边的低处向高海拔的格子爬。很多人第一反应会写成因为心里想的是“水往低处流”。但注意这里是从终点往回逆推——海边是起点海拔低要逆流而上就必须往海拔更高或相等的方向走。想清楚这个逻辑就不会写反了。4.5 建造最大岛屿时合并岛屿不去重这个问题在上面已经详细说过了。同一个0格子四面都贴着同一个岛屿时如果直接累加map[id]同一个岛屿会被加四次结果莫名变成原始面积*41。用unordered_set去重后才是真正的合并面积。调试时如果发现答案偏大且总是4倍关系基本就是这个原因。4.6 编号数组和原数组混用建造最大岛屿这题里grid数组仍然保存原始的0/1而islandMark保存岛屿编号。两个数组职责不同一定不能混用。如果在判断某个格子是否属于某岛屿时用grid的值判断编号结果全是1必然出错。提示做题时建议给每个数组起一个含义明确的名字比如grid、islandMark、visited、areaMap一眼能看出用途。省去调试时反复回去看声明的功夫。5. 我个人的刷题复盘心得到第五十七天图论的基础DFS/BFS其实已经练得比较扎实了今天的四道题更像是“从基础到应用”的一次集中检验。我做下来最大的感受是边界判断贯穿了所有坑。孤岛问题考的是“边界上的陆地”水流问题考的是“边界出发的反向探索”建造最大岛屿则考的是“边界合并的潜在面积”每道题都在和“边”打交道。我建议把这几道题放在一起二刷重点不是把代码背下来而是看自己能否在拿到新题时快速识别“这题是从边界入手还是从内部入手”。另外今天的所有解法我都只用了DFS但BFS版本建议也各写一遍。不是说要掌握所有写法而是当你DFS写熟了之后用BFS重写能帮助理解两种遍历方式的差异。一旦遇到“逐层扩散”类的题目最短路径、一层层感染等这个BFS的手感就会派上用场。我个人在实际操作中的一个经验是第一遍刷完这些题后可以自己在上面的代码基础上加打印信息比如每块岛屿的面积是多少、编号是多少、边界连通块有哪些多打印几次就能把所有内部逻辑理清楚。等到真的上了笔试或者机考这些打印代码就是你的debug利器。最后再分享一个小技巧如果你发现自己在某一类图论题上反复踩坑就单独整理一个“图论边界检查清单”把上面这些常见问题列进去每次提交前逐项过一遍可以省下大量罚时。