LeetCode - 200 岛屿数量-蒲公英云

LeetCode - 200 岛屿数量

题目来源

200. 岛屿数量 - 力扣（LeetCode）

题目描述

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

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

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

示例

输入	grid = [ [“1”,”1”,”1”,”1”,”0”], [“1”,”1”,”0”,”1”,”0”], [“1”,”1”,”0”,”0”,”0”], [“0”,”0”,”0”,”0”,”0”] ]
输出	1

输入	grid = [ [“1”,”1”,”0”,”0”,”0”], [“1”,”1”,”0”,”0”,”0”], [“0”,”0”,”1”,”0”,”0”], [“0”,”0”,”0”,”1”,”1”] ]
输出	3

提示

题目分析

本题也是一道连通图问题，可以考虑使用并查集求解。

和华为机试 - 发广播_伏城之外的博客-CSDN博客

以及LeetCode - 547 省份数量_伏城之外的博客-CSDN博客

的区别在于，前面两道题都是直接给出了点与点之间的连接关系，而本题并没有给出，需要我们自己求解。

因此本题的难度要大于前面两题。

我们需要先求解grid中陆地（即1）与陆地的连接关系，然后才能执行并查集的合并逻辑。

首先，我们需要创建一个并查集结构，即一个一维数组fa，fa有n*m个元素，其中n,m分别对应grid矩阵的行数和列数。

初始化时，fa[k] = i*m + j，k取值范围是[0, n*m-1]，fa和grid的对应关系如下

这样的话，我们就将一个二维关系，转为了一维关系。

然后，就可以分析grid中陆地与陆地之间的连接关系了：

首先需要判断grid[i][j]是否1，即是否为陆地，若是，则继续下面逻辑：

陆地的连接关系，有四个方向，即上下左右，我们需要对每一个陆地的上下左右进行连接分析：

假设grid[i][j]是陆地，分别判断

其上边，grid[i-1][j]，是否为陆地，若为陆地，则fa数组的第 i*m+j 个和第 (i-1)*m+j 是连接的，我们将它们合并。

其下边，grid[i+1][j]，判断同上

其左边，grid[i][j-1]，判断同上

其右边，grid[i][j+1]，判断同上

在分析完所有陆地的连接关系后，我们就可以定义并查集的合并和查找功能了具体实现和以前相同，不知道的小伙伴可以去看前面

华为机试 - 发广播_伏城之外的博客-CSDN博客

中关于并查集的合并以及查找功能实现的原理。

最后，就是求解grid中有几块独立的陆地？

这里需要注意的是，初始化并查集时，我们假设grid元素全部都是陆地，且每个陆地都互不相连（PS：这里大家要以并查集结构的思维来看，fa数组中每个数组元素都指向自己，因此所有陆地偶都互不相连），此时共有count = n*m个独立陆地。

当并查集将两块路径进行合并后，即count—。

但是并查集合并完后，最终count中还包含水区域，因此count还需要减去水区域的个数，这样count的数目才是独立陆地的数目。

算法源码

/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function (grid) {
  let n = grid.length;
  let m = grid[0].length;
  const ufs = new UnionFindSet(n, m);
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
      if (grid[i][j] === "1") {
        if (j - 1 >= 0 && grid[i][j - 1] === "1") {
          ufs.union(i * m + j - 1, i * m + j);
        }
        if (i - 1 >= 0 && grid[i - 1][j] === "1") {
          ufs.union((i - 1) * m + j, i * m + j);
        }
        if (j + 1 < m && grid[i][j + 1] === "1") {
          ufs.union(i * m + j, i * m + j + 1);
        }
        if (i + 1 < n && grid[(i + 1, j)] === "1") {
          ufs.union(i * m + j, (i + 1) * m + j);
        }
      } else {
        ufs.count--;
      }
    }
  }
  return ufs.count;
};
class UnionFindSet {
  constructor(n, m) {
    this.fa = [];
    this.init(n, m);
    this.count = n * m;
  }
  init(n, m) {
    for (let i = 0; i < n * m; i++) {
      this.fa[i] = i;
    }
  }
  find(x) {
    if (x !== this.fa[x]) {
      this.fa[x] = this.find(this.fa[x]);
      return this.fa[x];
    }
    return x;
  }
  union(x, y) {
    let x_fa = this.find(x);
    let y_fa = this.find(y);
    if (x_fa !== y_fa) {
      this.fa[y_fa] = x_fa;
      this.count--;
    }
  }
}