← 返回完整题库
JavaScript困难

给定一个由 '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);注意会修改入参(需保留时复制)。

本题来自 计算机知识面试题库,共 921 道题。