一、题目详解
问题描述
给定一个由 '1'（陆地）和 '0'（水）组成的二维网格，计算岛屿的数量。岛屿由相邻的陆地连接形成，相邻指水平方向或垂直方向（斜向相邻的陆地不视为同一岛屿）。网格的边界和边缘均被水包围。
示例
输入：
grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]输出： 1（整个网格中只有一个连通的岛屿）
输入：
grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]输出： 3（三个独立的岛屿）
二、解题思路
岛屿问题的核心是寻找连通分量：每个岛屿本质上是一个由'1'组成的连通分量，因此问题可转化为统计网格中'1'的连通分量数量。
解决连通分量问题的经典方法有两种：深度优先搜索（DFS） 和广度优先搜索（BFS）。两种方法的核心逻辑一致：
-
遍历网格中的每个单元格；
-
当遇到未访问的
'1'时，启动一次搜索（DFS/BFS），将所有与该'1'连通的'1'标记为 “已访问”； -
每次启动搜索即对应一个新岛屿，计数器加 1。
三、具体实现
方法一：深度优先搜索（DFS）
核心思想
使用递归遍历与当前'1'相邻的所有'1'（上下左右四个方向），并将访问过的'1'标记为'0'（避免重复访问），直到所有连通的'1'都被标记。
C++ 代码实现
class Solution {
private:
// 递归函数：深度优先搜索并标记连通的陆地
void dfs(vector<vector<char>>& grid, int row, int column) {
int nr = grid.size(); // 网格行数
int nc = grid[0].size(); // 网格列数
// 将当前陆地标记为已访问（改为'0'）
grid[row][column] = '0';
// 向上搜索
if (row - 1 >= 0 && grid[row - 1][column] == '1') {
dfs(grid, row - 1, column);
}
// 向下搜索
if (row + 1 < nr && grid[row + 1][column] == '1') {
dfs(grid, row + 1, column);
}
// 向左搜索
if (column - 1 >= 0 && grid[row][column - 1] == '1') {
dfs(grid, row, column - 1);
}
// 向右搜索
if (column + 1 < nc && grid[row][column + 1] == '1') {
dfs(grid, row, column + 1);
}
}
public:
int numIslands(vector<vector<char>>& grid) {
if (grid.empty())
return 0; // 空网格直接返回0
int nr = grid.size();
int nc = grid[0].size();
int numIslands = 0;
// 遍历所有单元格
for (int r = 0; r < nr; r++) {
for (int c = 0; c < nc; c++) {
if (grid[r][c] == '1') { // 发现未访问的陆地
numIslands++; // 岛屿数量加1
dfs(grid, r, c); // 标记所有连通的陆地
}
}
}
return numIslands;
}
};关键细节
-
标记已访问：通过将
'1'改为'0'，避免使用额外空间存储访问状态，节省内存。 -
边界检查：每次递归前需判断坐标是否在网格范围内（如
row - 1 >= 0），防止数组越界。
方法二：广度优先搜索（BFS）
核心思想
使用队列存储待访问的陆地坐标，每次从队列中取出一个坐标，遍历其上下左右四个方向的相邻单元格。若相邻单元格是未访问的'1'，则加入队列并标记为已访问，直到队列为空（当前岛屿的所有陆地均被标记）。
Java 代码实现
// 辅助类：存储坐标
class Coordinate {
int x, y;
public Coordinate(int x, int y) {
this.x = x;
this.y = y;
}
}
public class Solution {
// 方向数组：上下左右四个方向（dx, dy）
int[] deltaX = { 0, 1, -1, 0 };
int[] deltaY = { 1, 0, 0, -1 };
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0)
return 0;
if (grid[0] == null || grid[0].length == 0)
return 0;
int islands = 0;
int n = grid.length; // 行数
int m = grid[0].length; // 列数
boolean[][] visited = new boolean[n][m]; // 标记访问状态
// 遍历所有单元格
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// 发现未访问的陆地
if (grid[i][j] == '1' && !visited[i][j]) {
bfs(grid, i, j, visited); // 标记所有连通的陆地
islands++; // 岛屿数量加1
}
}
}
return islands;
}
// 广度优先搜索
private void bfs(char[][] grid, int x, int y, boolean[][] visited) {
Queue<Coordinate> queue = new ArrayDeque<>();
queue.offer(new Coordinate(x, y)); // 起始坐标入队
visited[x][y] = true; // 标记为已访问
while (!queue.isEmpty()) {
Coordinate coor = queue.poll(); // 取出队首坐标
// 遍历四个方向
for (int direction = 0; direction < 4; direction++) {
int newX = coor.x + deltaX[direction];
int newY = coor.y + deltaY[direction];
// 检查新坐标是否有效（在网格内、未访问、是陆地）
if (isValid(grid, newX, newY, visited)) {
queue.offer(new Coordinate(newX, newY));
visited[newX][newY] = true;
}
}
}
}
// 验证坐标有效性
private boolean isValid(char[][] grid, int x, int y, boolean[][] visited) {
int n = grid.length;
int m = grid[0].length;
// 坐标越界
if (x < 0 || x >= n || y < 0 || y >= m)
return false;
// 已访问过
if (visited[x][y])
return false;
// 不是陆地
return grid[x][y] == '1';
}
}关键细节
-
方向数组：通过
deltaX和deltaY简化四个方向的坐标计算，避免重复代码。 -
访问标记：使用
visited数组记录访问状态（与 DFS 的原地修改方式不同，适用于原网格不可修改的场景）。
四、复杂度分析
时间复杂度
两种方法的时间复杂度均为 O(M×N)，其中 M 为网格行数，N 为网格列数。每个单元格最多被访问一次。
空间复杂度
-
DFS：最坏情况下（网格全为陆地），递归栈深度为 O (M×N)，因此空间复杂度为 O (M×N)。
-
BFS：最坏情况下，队列中最多存储 O (min (M,N)) 个坐标（如网格为正方形且全为陆地时，队列最大长度为对角线长度），但通常简化为 O (M×N)。
五、总结
岛屿数量问题是连通分量搜索的典型应用，核心在于：
-
遍历网格发现未访问的陆地；
-
通过 DFS 或 BFS 标记所有连通的陆地；
-
统计搜索启动次数即得到岛屿数量。
-
DFS 实现简洁，适合递归友好的场景，但需注意递归栈溢出风险（可改用迭代式 DFS 避免）。
-
BFS 适合大规模网格，通过队列控制访问顺序，避免栈溢出问题。
掌握这两种方法后，可轻松解决类似的网格搜索问题（如 “岛屿的最大面积”“被围绕的区域” 等）。