LeetCode 「中等」200.岛屿数量
题目描述
给你一个由 '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
解答
DFS（深度优先搜索）
关键思路
DFS 的核心思想是通过递归的方式，从一个起点开始，尽可能“深”地探索，直到无法继续为止。对于岛屿问题，DFS 会从一个陆地单元格触发，沿着上下左右四个方向递归地访问所有相邻的陆地单元格，直到所有相连的陆地都被标记为访问过。
具体步骤
- 遍历矩阵
- 遍历矩阵的每个单元格，寻找值为
'1'的陆地单元格 - 每次发现一个
'1'，表示发现了一个岛屿，计数器加 1
- 启动 DFS
- 当发现一个陆地单元格时，从该单元格开始调用 DFS 函数
- DFS 函数逻辑
- 边界检查：检查当前单元格是否超出矩阵范围，或者是否已经是水（值为
'0'）。如果是，则直接返回 - 标记访问：将当前单元格标记为访问过（将其值改为
'0'） - 递归访问相邻单元格：依次递归访问当前单元格的上下左右四个方向的相邻单元格，递归调用 DFS 函数
- 重复步骤
- 继续遍历矩阵，直到所有单元格都被检查过
Code
/**
* @param {character[][]} grid
* @return {number}
*/
var numIslands = function(grid) {
if (!grid.length) return 0;
const row = grid.length;
const col = grid[0].length;
let islandcnt = 0;
var dfs = function (r, c) {
if (r < 0 || r >= row || c < 0 || c >= col || grid[r][c] !== '1') return;
grid[r][c] = '0';
dfs(r - 1, c); // 上
dfs(r + 1, c); // 下
dfs(r, c - 1); // 左
dfs(r, c + 1); // 右
}
for (let i = 0; i < row; ++i) {
for (let j = 0; j < col; ++j) {
// 发现岛屿
if (grid[i][j] === '1') {
dfs(i, j);
islandcnt++;
}
}
}
return islandcnt;
};
BFS（广度优先搜索）
关键思路
BFS 的核心思想是通过队列逐层遍历。从一个起点开始，先访问所有相邻的单元格，再访问下一层的相邻单元格。对于岛屿问题，BFS 会从一个陆地单元格触发，逐层标记所有相连的陆地单元格，直到队列为空。
具体步骤
- 遍历矩阵
- 遍历矩阵的每个单元格，寻找值为
'1'的陆地单元格 - 每次发现一个
'1'，表示发现了一个岛屿，计数器加 1
- 启动 BFS
- 当发现一个陆地单元格时，从该单元格开始调用 BFS 函数
- BFS 函数逻辑
- 初始化队列：将当前单元格的坐标加入队列
- 逐层遍历：
- 从队列中取出一个单元格
- 检查该单元格的上下左右四个方向的相邻单元格
- 如果相邻单元格是陆地（值为
'1'），将其标记为访问过（值改为'0'），并将其坐标加入队列
- 重复上述过程，直到队列为空，表示当前岛屿的所有陆地单元格都被访问过
- 重复步骤
- 继续遍历矩阵，直到所有单元格都被检查过
Code
var bfs = function(r, c) {
const queue = [[r, c]];
grid[r][c] = '0';
while(queue.length) {
const [curR, curC] = queue.shift();
const directions = [[-1, 0], [1, 0], [0, -1], [0 , 1]]; // 四个方向
for(const [dr, dc] of directions) {
const newR = curR + dr;
const newC = curC + dc;
if (newR >= 0 && newR < row && newC >= 0 && newC < col && grid[newR][newC] === '1') {
queue.push([newR, newC]);
grid[newR][newC] = '0';
}
}
}
}