岛屿数量

Posted on Edited on In ,

题目

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

示例 1：
输入：

1
2
3
4
5
6
grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]

输出：1

示例 2：
输入：

1
2
3
4
5
6
grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]

输出：3  

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] 的值为 ‘0’ 或 ‘1’

解1

思路：将相连的 1 加入同一个集合，如果两个 1 相连则把他们所属的集合合并。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
function numsIslands(grid){
  // 建立 `1`的坐标到其所属岛屿的映射
  const posToIlands = {};
  for(let i = 0; i < grid.length; i++){
    for(let j = 0; j < grid.length; j++){
      if(grid[i][j] === '0') return;

      posToIlands[`${i}-${j}`] = [`${i}-${j}`];
      if(grid[i - 1][j] === '1'){
        const merged = posToIlands[`${i - 1}-${j}`].concat([`${i}-${j}`])
        posToIlands[`${i}-${j}`] = merged;
        posToIlands[`${i}-${j}`] = merged;
      }
      if(grid[i][j - 1] === '1'){
        const merged = posToIlands[`${i - 1}-${j}`].concat([`${i}-${j}`])
        posToIlands[`${i}-${j}`] = merged;
        posToIlands[`${i}-${j}`] = merged;
      }
    }
  }

  for(let key in posToIlands){
    
  }
}