一、DFS 岛屿问题核心思想岛屿问题本质是二维网格 DFS 洪水填充遍历网格每一个位置遇到陆地 (1)以当前点为起点向上下左右四个方向递归遍历遍历过的陆地原地标记为海洋 (0)避免重复访问完整走完一片连通陆地即为一个岛屿二、通用前置模板方向数组四个移动方向上、下、左、右刷题标准写法// 方向数组行偏移、列偏移 int dir[4][2] {{-1,0}, {1,0}, {0,-1}, {0,1}};三、基础 DFS 递归函数模板// grid二维网格x,y当前坐标m/n行列总数 void dfs(vectorvectorchar grid, int x, int y, int m, int n) { // 越界判定坐标不在网格内直接返回 if(x 0 || x m || y 0 || y n) return; // 当前不是陆地返回 if(grid[x][y] ! 1) return; // 标记已访问陆地改为海洋 grid[x][y] 0; // 遍历四个方向递归搜索 for(int i 0; i 4; i) { int nx x dir[i][0]; int ny y dir[i][1]; dfs(grid, nx, ny, m, n); } }四、经典例题 1岛屿数量LeetCode 200题目描述给定由1陆地和0海洋组成的二维网格计算岛屿总数。陆地相邻为上下左右斜向不算。完整可运行代码#include iostream #include vector using namespace std; int dir[4][2] {{-1,0},{1,0},{0,-1},{0,1}}; void dfs(vectorvectorchar grid, int x, int y, int m, int n) { if(x 0 || x m || y 0 || y n || grid[x][y] ! 1) return; grid[x][y] 0; for(int i 0; i 4; i) { int nx x dir[i][0]; int ny y dir[i][1]; dfs(grid, nx, ny, m, n); } } int numIslands(vectorvectorchar grid) { if(grid.empty()) return 0; int m grid.size(); int n grid[0].size(); int count 0; // 遍历整个网格 for(int i 0; i m; i) { for(int j 0; j n; j) { if(grid[i][j] 1) { count; dfs(grid, i, j, m, n); } } } return count; } int main() { vectorvectorchar grid { {1,1,0,0,0}, {1,1,0,0,0}, {0,0,1,0,0}, {0,0,0,1,1} }; cout 岛屿数量 numIslands(grid) endl; return 0; }五、经典例题 2最大岛屿面积题目描述求网格中面积最大的岛屿面积为陆地单元格数量。int dir[4][2] {{-1,0},{1,0},{0,-1},{0,1}}; int dfsArea(vectorvectorint grid, int x, int y, int m, int n) { if(x 0 || x m || y 0 || y n || grid[x][y] 0) return 0; grid[x][y] 0; int area 1; // 当前单元格面积 for(int i 0; i 4; i) { int nx x dir[i][0]; int ny y dir[i][1]; area dfsArea(grid, nx, ny, m, n); } return area; } int maxAreaOfIsland(vectorvectorint grid) { if(grid.empty()) return 0; int m grid.size(); int n grid[0].size(); int maxArea 0; for(int i 0; i m; i) { for(int j 0; j n; j) { if(grid[i][j] 1) { int cur dfsArea(grid, i, j, m, n); maxArea max(maxArea, cur); } } } return maxArea; }六、岛屿类题目通用解题步骤定义四方向数组控制遍历方向编写 DFS 函数先判越界 判非陆地再标记访问四个方向递归扩散双层循环遍历整张网格遇到陆地就启动 DFS根据题目要求计数 / 求面积 / 求周长等七、DFS 岛屿题拓展题型岛屿周长封闭岛屿被围绕的区域图像渲染颜色填充网格中的路径搜索八、新手易错点忘记边界越界判断数组下标越界崩溃遍历后不修改原网格造成重复遍历、死递归方向数组写错漏方向 / 多方向行列 m、n 混淆判断条件颠倒九、DFS 优缺点回顾优点代码简短、逻辑直观洪水填充首选缺点网格极大时递归深度过深栈溢出此时改用 BFS十、今日总结岛屿问题 二维网格 DFS 洪水填充四方向数组是标准配置务必熟记原地修改网格标记访问无需额外 visited 数组岛屿数量、最大面积是两大入门必背模板
DFS岛屿问题：核心思想与实战模板
一、DFS 岛屿问题核心思想岛屿问题本质是二维网格 DFS 洪水填充遍历网格每一个位置遇到陆地 (1)以当前点为起点向上下左右四个方向递归遍历遍历过的陆地原地标记为海洋 (0)避免重复访问完整走完一片连通陆地即为一个岛屿二、通用前置模板方向数组四个移动方向上、下、左、右刷题标准写法// 方向数组行偏移、列偏移 int dir[4][2] {{-1,0}, {1,0}, {0,-1}, {0,1}};三、基础 DFS 递归函数模板// grid二维网格x,y当前坐标m/n行列总数 void dfs(vectorvectorchar grid, int x, int y, int m, int n) { // 越界判定坐标不在网格内直接返回 if(x 0 || x m || y 0 || y n) return; // 当前不是陆地返回 if(grid[x][y] ! 1) return; // 标记已访问陆地改为海洋 grid[x][y] 0; // 遍历四个方向递归搜索 for(int i 0; i 4; i) { int nx x dir[i][0]; int ny y dir[i][1]; dfs(grid, nx, ny, m, n); } }四、经典例题 1岛屿数量LeetCode 200题目描述给定由1陆地和0海洋组成的二维网格计算岛屿总数。陆地相邻为上下左右斜向不算。完整可运行代码#include iostream #include vector using namespace std; int dir[4][2] {{-1,0},{1,0},{0,-1},{0,1}}; void dfs(vectorvectorchar grid, int x, int y, int m, int n) { if(x 0 || x m || y 0 || y n || grid[x][y] ! 1) return; grid[x][y] 0; for(int i 0; i 4; i) { int nx x dir[i][0]; int ny y dir[i][1]; dfs(grid, nx, ny, m, n); } } int numIslands(vectorvectorchar grid) { if(grid.empty()) return 0; int m grid.size(); int n grid[0].size(); int count 0; // 遍历整个网格 for(int i 0; i m; i) { for(int j 0; j n; j) { if(grid[i][j] 1) { count; dfs(grid, i, j, m, n); } } } return count; } int main() { vectorvectorchar grid { {1,1,0,0,0}, {1,1,0,0,0}, {0,0,1,0,0}, {0,0,0,1,1} }; cout 岛屿数量 numIslands(grid) endl; return 0; }五、经典例题 2最大岛屿面积题目描述求网格中面积最大的岛屿面积为陆地单元格数量。int dir[4][2] {{-1,0},{1,0},{0,-1},{0,1}}; int dfsArea(vectorvectorint grid, int x, int y, int m, int n) { if(x 0 || x m || y 0 || y n || grid[x][y] 0) return 0; grid[x][y] 0; int area 1; // 当前单元格面积 for(int i 0; i 4; i) { int nx x dir[i][0]; int ny y dir[i][1]; area dfsArea(grid, nx, ny, m, n); } return area; } int maxAreaOfIsland(vectorvectorint grid) { if(grid.empty()) return 0; int m grid.size(); int n grid[0].size(); int maxArea 0; for(int i 0; i m; i) { for(int j 0; j n; j) { if(grid[i][j] 1) { int cur dfsArea(grid, i, j, m, n); maxArea max(maxArea, cur); } } } return maxArea; }六、岛屿类题目通用解题步骤定义四方向数组控制遍历方向编写 DFS 函数先判越界 判非陆地再标记访问四个方向递归扩散双层循环遍历整张网格遇到陆地就启动 DFS根据题目要求计数 / 求面积 / 求周长等七、DFS 岛屿题拓展题型岛屿周长封闭岛屿被围绕的区域图像渲染颜色填充网格中的路径搜索八、新手易错点忘记边界越界判断数组下标越界崩溃遍历后不修改原网格造成重复遍历、死递归方向数组写错漏方向 / 多方向行列 m、n 混淆判断条件颠倒九、DFS 优缺点回顾优点代码简短、逻辑直观洪水填充首选缺点网格极大时递归深度过深栈溢出此时改用 BFS十、今日总结岛屿问题 二维网格 DFS 洪水填充四方向数组是标准配置务必熟记原地修改网格标记访问无需额外 visited 数组岛屿数量、最大面积是两大入门必背模板
