[200] 岛屿数量

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例 1：

输入：grid = [

["1","1","1","1","0"],

["1","1","0","1","0"],

["1","1","0","0","0"],

["0","0","0","0","0"]

]

输出：1

示例 2：

输入：grid = [

["1","1","0","0","0"],

["1","1","0","0","0"],

["0","0","1","0","0"],

["0","0","0","1","1"]

]

输出：3

这道题是经典的岛屿问题基础，所有的岛屿问题都可以归类为统一解决框架。即：判断当前节点是否被访问过，并分别对其连接节点进行深度遍历搜索，找到所有的联通点。

我们可以先建立一个 visited 二维数组，用于记录每一个节点是否被访问过。

接下来遍历 grid 的每一个节点，若当前节点是陆地，且之前未被访问过，则认为这是一块新岛屿， 结果 + 1。

之后使用 DFS 遍历其上下左右节点，访问到该岛屿上的所有节点，将这些位置的 visited 设为 true。

function numIslands(grid: string[][]): number {
  let res = 0;
  const height = grid.length;
  const width = grid[0].length;
  const visited: boolean[][] = Array(height)
    .fill(0)
    .map(x => Array(width).fill(false));

  for (let i = 0; i < height; i++) {
    for (let j = 0; j < width; j++) {
      if (grid[i][j] === '1' && !visited[i][j]) {
        res += 1;
        floodFill(i, j);
      }
    }
  }

  return res;

  function floodFill(i: number, j: number) {
    // 递归越界返回
    if (i < 0 || j < 0 || i >= height || j >= width) return;
    // 已遍历过，或者当前节点不是陆地时，返回
    if (visited[i][j] || grid[i][j] === '0') return;

    // 将当前点设置为已访问
    visited[i][j] = true;

    // 分别递归其上下左右节点
    floodFill(i - 1, j);
    floodFill(i + 1, j);
    floodFill(i, j - 1);
    floodFill(i, j + 1);
  }
}

当然，在本题中，其实可以不必要多维护一个 visited 数组。

由于 grid 中的每一个节点不会被二次使用到，我们可以直接改动原 grid 数组，将已访问过的陆地节点设置为 "0"，将该陆地淹没，这样实现的效果完全相同。

function numIslands(grid: string[][]): number {
  let res = 0;
  const height = grid.length;
  const width = grid[0].length;
  for (let i = 0; i < height; i++) {
    for (let j = 0; j < width; j++) {
      if (grid[i][j] === '1') {
        res += 1;
        floodFill(i, j);
      }
    }
  }
  return res;

  function floodFill(i: number, j: number) {
    // 递归越界返回
    if (i < 0 || j < 0 || i >= height || j >= width) return;
    // 已遍历过，或者当前节点不是陆地时，返回
    if (grid[i][j] === '0') return;

    // 将当前点设置为已访问
    grid[i][j] = '0';

    // 分别递归其上下左右节点
    floodFill(i - 1, j);
    floodFill(i + 1, j);
    floodFill(i, j - 1);
    floodFill(i, j + 1);
  }
}