200 - 岛屿数量

题目链接

200. 岛屿数量

题目

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。此外，你可以假设该网格的四条边均被水包围。

思路

岛屿数量就是连通子图的数量。要完整地遍历一个连通子图，我们可以使用DFS或者BFS，我使用的是DFS。遍历完一个连通子图后，这个连通子图所有的点的值都要从0变成1，这样就可以防止重复遍历。

解题方法

1. 遍历每个节点进行判断，这个点是1还是0。
2. 如果是1，那么这个点就在一个连通子图中，我们使用DFS遍历整个连通子图，并将连通子图中所有的点变为0。result ++;
3. 如果是0，就倒下一个点。
4. DFS的递归条件是这个点的上下左右是否是1，因为这才是连接起来的陆地。注意坐标的范围。

复杂度

• 时间复杂度: 假设有 $M \times N$个节点，那么时间复杂度就是 $O(M \times N)$。

• 空间复杂度: 最坏情况下，当所有的节点都是"1"，递归的深度等于网格的大小，那么递归调用栈的大小就是 $O(M \times N)$。

代码

/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function(grid) {
  function dfs(row, col) {
    const height = grid.length;
    const width = grid[0].length;

    grid[row][col] = "0";

    if(row + 1 < height && grid[row + 1][col] === "1") dfs(row + 1, col);
    if(row - 1 >= 0 && grid[row - 1][col] === "1") dfs(row - 1, col);
    if(col + 1 < width && grid[row][col + 1] === "1") dfs(row, col + 1);
    if(col - 1 >= 0 && grid[row][col - 1] === "1") dfs(row, col - 1);
  }
  let result = 0;
  for(let row = 0; row < grid.length; row ++) {
    for(let col = 0; col < grid[0].length; col ++) {
      if(grid[row][col] === "1") {
        result ++;
        dfs(row, col);
      }
    }
  }
  return result;
};