给定一个由 '1'(陆地)和 '0'(水)组成的的二维网格,计算岛屿的数量(岛屿问题)
参考答案
DFS/BFS 淹没法:
function numIslands(grid) {
let count = 0;
const dfs = (i, j) => {
if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] !== '1') return;
grid[i][j] = '0'; // 标记访问
dfs(i + 1, j); dfs(i - 1, j); dfs(i, j + 1); dfs(i, j - 1);
};
for (let i = 0; i < grid.length; i++)
for (let j = 0; j < grid[0].length; j++)
if (grid[i][j] === '1') { count++; dfs(i, j); }
return count;
}
要点:四连通、标记已访问(改值或 visited)、BFS 用队列避免深递归、复杂度 O(m*n);注意会修改入参(需保留时复制)。