计算岛屿的数量

一、题目

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

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

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

示例 1:
输入:
11110
11010
11000
00000
输出: 1

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/number-of-islands
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二、思路

连城一片岛屿的情况如下图所示：

由上图可知，岛屿形成的条件是上下左右都是 1

如果出现了一个为 0，则不算

因此可以选择用深度优先搜索，查找树中节点为 1 的情况，若当前节点为 1，则向下继续查找，直到末端，算为一个岛屿

否则，继续遍历树的节点，重复以上操作，返回岛屿数量。

三、题解

/**
 * @param {character[][]} grid
 * @return {number}
 */
// 深度优先搜索 DFS
var dfs = function (grid, r, c) {
  const [nr, nc] = [grid.length, grid[0].length];
  grid[r][c] = '0';
  if (r - 1 >= 0 && grid[r - 1][c] === '1') dfs(grid, r - 1, c);
  if (r + 1 < nr && grid[r + 1][c] === '1') dfs(grid, r + 1, c);
  if (c - 1 >= 0 && grid[r][c - 1] === '1') dfs(grid, r, c - 1);
  if (c + 1 < nc && grid[r][c + 1] === '1') dfs(grid, r, c + 1);
};

var numIslands = function (grid) {
  const nr = grid.length;
  if (!nr) return 0;
  const nc = grid[0].length;
  let num_isLands = 0;
  for (let r = 0; r < nr; ++r) {
    for (let c = 0; c < nc; ++c) {
      if (grid[r][c] === '1') {
        num_isLands += 1;
        dfs(grid, r, c);
      }
    }
  }
  return num_isLands;
};

const test1 = [
  ['1', '1', '1', '1', '0'],
  ['1', '1', '0', '1', '0'],
  ['1', '1', '0', '0', '0'],
  ['0', '0', '0', '0', '0'],
];
const test2 = [
  ['1', '1', '0', '0', '0'],
  ['1', '1', '0', '0', '0'],
  ['0', '0', '1', '0', '0'],
  ['0', '0', '0', '1', '1'],
];

const test4 = [
  ['1', '1', '1', '1', '1'],
  ['1', '1', '1', '1', '1'],
  ['1', '1', '1', '1', '1'],
  ['1', '1', '1', '1', '1'],
];

const res1 = numIslands(test1);
const res2 = numIslands(test2);
const res3 = numIslands([]);
const res4 = numIslands(test4);
console.log(res1);
console.log(res2);
console.log(res3);
console.log(res4);