一、DFS 岛屿问题核心思想

岛屿问题本质是二维网格 DFS + 洪水填充

1. 遍历网格每一个位置
2. 遇到陆地 (1)，以当前点为起点向上下左右四个方向递归遍历
3. 遍历过的陆地原地标记为海洋 (0)，避免重复访问
4. 完整走完一片连通陆地，即为一个岛屿

二、通用前置模板（方向数组）

四个移动方向：上、下、左、右，刷题标准写法

// 方向数组：行偏移、列偏移 int dir[4][2] = {{-1,0}, {1,0}, {0,-1}, {0,1}};

三、基础 DFS 递归函数模板

// grid：二维网格，x,y：当前坐标，m/n：行列总数 void dfs(vector<vector<char>>& 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(vector<vector<char>>& 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(vector<vector<char>>& 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() { vector<vector<char>> 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(vector<vector<int>>& 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(vector<vector<int>>& 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; }

六、岛屿类题目通用解题步骤

1. 定义四方向数组，控制遍历方向
2. 编写 DFS 函数：先判越界 + 判非陆地，再标记访问
3. 四个方向递归扩散
4. 双层循环遍历整张网格，遇到陆地就启动 DFS
5. 根据题目要求：计数 / 求面积 / 求周长等

七、DFS 岛屿题拓展题型

1. 岛屿周长
2. 封闭岛屿
3. 被围绕的区域
4. 图像渲染（颜色填充）
5. 网格中的路径搜索

八、新手易错点

1. 忘记边界越界判断，数组下标越界崩溃
2. 遍历后不修改原网格，造成重复遍历、死递归
3. 方向数组写错，漏方向 / 多方向
4. 行列 m、n 混淆，判断条件颠倒

九、DFS 优缺点回顾

• 优点：代码简短、逻辑直观，洪水填充首选
• 缺点：网格极大时，递归深度过深栈溢出，此时改用 BFS

十、今日总结

1. 岛屿问题 = 二维网格 DFS + 洪水填充
2. 四方向数组是标准配置，务必熟记
3. 原地修改网格标记访问，无需额外 visited 数组
4. 岛屿数量、最大面积是两大入门必背模板