网格中的岛屿问题

网格为什么可以当作图处理？

• 顶点: 每个格子;
• 边: 相邻 (上下左右) 且取值相同的格子之间存在边;
• 结论: 连通块问题可以直接在网格上做 DFS/BFS, 不需要显式建图;

岛屿问题的 DFS 模板是什么？

• 越界或不是陆地时立即返回 0;
• 访问后把陆地改成水 (或写入 visited), 避免重复访问与死循环;
• 向四个方向递归并把结果累加;

const dfs = (grid, i, j) => {
  if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] !== "1") return 0;
  grid[i][j] = "2";
  return 1 + dfs(grid, i + 1, j) + dfs(grid, i - 1, j) + dfs(grid, i, j + 1) + dfs(grid, i, j - 1);
};

如何统计岛屿数量？

• 做法: 遍历每个格子, 遇到未访问的陆地就调用一次 DFS, 计数加一;
• 原理: 一次 DFS 会淹没整个连通块, 所以计数等于连通块数量;

const numIslands = function (grid) {
  let count = 0;
  for (let i = 0; i < grid.length; i++) {
    for (let j = 0; j < grid[0].length; j++) {
      if (grid[i][j] === "1") {
        dfs(grid, i, j);
        count++;
      }
    }
  }
  return count;
};

如何求最大岛屿面积？

• 差异: 让 DFS 返回本次淹没的格子数量, 即该连通块的面积;
• 结果: 对所有连通块取面积最大值;

const maxAreaOfIsland = function (grid) {
  let res = 0;
  for (let i = 0; i < grid.length; i++) {
    for (let j = 0; j < grid[0].length; j++) {
      if (grid[i][j] === 1) res = Math.max(res, dfs(grid, i, j));
    }
  }
  return res;
};

复杂度与易错点是什么？

• 复杂度: 时间 O(m * n), 每个格子最多访问一次; 空间 O(m * n) 递归栈;
• 易错: 两道题的陆地标记不同 (字符串 "1" 与数字 1), 判定条件要跟着改;
• 染色值选择: 用与陆地、水都不同的值 (如 "2"、2) 标记, 避免把已访问格子当成水;