200. 岛屿数量

Difficulty
Medium
Tags
BFS
DFS
URL
https://leetcode-cn.com/problems/number-of-islands/
Star
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
示例 1：
输入：grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
输出：1
示例 2：
输入：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'
通过次数384,881提交次数679,894

法 1 BFS

思路
每找到一个1，就把该 1 周围的1 都标记一下，然后遍历 grid 看总共有多少个1
其中标记的过程 既可以用 BFS 也 可以用DFS
题解
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        res = 0
        visited = [[False] * len(grid[0]) for _ in grid]
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == "1" and not visited[i][j]:
                    res += 1
                    # 把该节点周围的都标记为 True
                    self.bfs(grid, i, j, visited)
        return res

    def bfs(self, grid, r, c, visited):
        queue = deque()
        queue.append((r,c))
        visited[r][c] = True
        dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]]
        while queue:
            cur_x, cur_y = queue.popleft()
            
            for d in dirs:
                x = cur_x + d[0]
                y = cur_y + d[1]

                if (len(grid) > x >= 0 and 
                    len(grid[0]) > y >= 0 and
                    grid[x][y] == "1" and 
                    not visited[x][y]):
                    visited[x][y] = True
                    queue.append((x, y))

法2 并查集

思路
将“1”周围的“1”进行union，然后再判断每个“1” 是否 在uf中为父节点
题解
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])
        uf = UnionFind(m*n)
        dirs = [(0, 1),  (1, 0)]
        for i in range(0, m):
            for j in range(0, n):
                if grid[i][j] == "1":
                    for d in dirs:
                        x, y = i + d[0], j + d[1]
                        if m > x >= 0 and n > y >= 0 and grid[x][y] == "1":
                            uf.union(i*n+j, x*n+y)
        
        res = 0
        for i in range(0, m):
            for j in range(0, n):
                if grid[i][j] == "1" and uf.find(i*n+j) == i*n+j:
                    res += 1

        return res

class UnionFind:
    def __init__(self, n):
        self.root = [i for i in range(n)]
        self.size = [0 for _ in range(n)]

    def find(self, x):
        if self.root[x] != x:
            self.root[x] = self.find(self.root[x])

        return self.root[x]

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x != root_y:
            if self.size[root_x] < self.size[root_y]:
                self.root[root_x] = root_y
                self.size[root_y] += self.size[root_x]
            else:
                self.root[root_y] = root_x
                self.size[root_x] += self.size[root_y]