当前位置：首页 > news >正文

DFS岛屿问题：核心思想与实战模板

news 2026/5/26 19:59:47

一、DFS 岛屿问题核心思想

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

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

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

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

// 方向数组：行偏移、列偏移 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; }