每天一道leetcode(Day 23)

200. 岛屿数量

题目描述

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

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

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

示例

• 示例 1:

输入:
11110
11010
11000
00000
输出: 1

• 示例  2:

输入:
11000
11000
00100
00011
输出: 3
解释: 每座岛屿只能由水平和/或竖直方向上相邻的陆地连接而成。

解题思路

如图，我们其实就是要求红色区域的个数，换句话说就是求连续区域的个数。

思路是用 DFS 来解：

• 建立一个 visited 数组用来记录某个位置是否被访问过。对于一个为 1 且未被访问过的位置，递归进入其上下左右位置上为 1 的数，将其 visited 变成 true。
• 找完相邻区域后，将结果 res 自增 1，然后再继续找下一个为 1 且未被访问过的位置，直至遍历完.

但是这道题目只用求连通区域的个数，因此不需要额外的空间去存储 visited 信息。
由上面的过程可知，在 DFS 过程中对于数字为 0 的其实不会进行操作， 因此对于已经访问的元素，将其置为 0 即可。

代码

/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function (grid) {
  let res = 0,
    rows = grid.length;
  if (rows === 0) return 0;
  const cols = grid[0].length;
  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      if (grid[i][j] === "1") {
        helper(grid, i, j, rows, cols);
        res++;
      }
    }
  }
  return res;
};
function helper(grid, i, j, rows, cols) {
  if (i < 0 || j < 0 || i > rows - 1 || j > cols - 1 || grid[i][j] === "0")
    return;
  grid[i][j] = "0";
  helper(grid, i - 1, j, rows, cols);
  helper(grid, i + 1, j, rows, cols);
  helper(grid, i, j - 1, rows, cols);
  helper(grid, i, j + 1, rows, cols);
}

参考

200. 岛屿数量