200. 岛屿数量

给你一个由 ‘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’

解法一：DFS

遍历地图中所有的节点，每当遇到一个陆地时，就用DFS将该陆地所在岛屿上的所有陆地都标记为已访问。

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])
        ans = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1':
                    ans += 1
                    stack = [(i, j)]
                    while stack:
                        x, y = stack.pop()
                        # mark the node as visited
                        grid[x][y] = '2'
                        if x > 0 and grid[x-1][y] == '1':
                            stack.append((x-1, y))
                        if x < m - 1 and grid[x+1][y] == '1':
                            stack.append((x+1, y))
                        if y > 0 and grid[x][y-1] == '1':
                            stack.append((x, y-1))
                        if y < n - 1 and grid[x][y+1] == '1':
                            stack.append((x, y+1))
        return ans

解法二：BFS

将DFS的部分改成队列即可实现BFS。

解法三：Union Find

使用并查集root记录每个节点的root索引。注意find时候会把寻找根节点时沿途的节点root索引都设置为真正的根（i == root[i]）。

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])
        uf = UnionFind(grid)
        waters = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '0':
                    waters += 1
                    continue
                current = n * i + j
                if i > 0 and grid[i-1][j] == '1':
                    neighbor = n * (i - 1) + j
                    uf.union(neighbor, current)
                if i < m - 1 and grid[i+1][j] == '1':
                    neighbor = n * (i + 1) + j
                    uf.union(neighbor, current)
                if j > 0 and grid[i][j-1] == '1':
                    neighbor = n * i + j - 1
                    uf.union(neighbor, current)
                if j < n - 1 and grid[i][j+1] == '1':
                    neighbor = n * i + j + 1
                    uf.union(neighbor, current)
        # 水应该从ans中减去
        return uf.get_count() - waters
class UnionFind:
    def __init__(self, grid):
        m, n = len(grid), len(grid[0])
        self.root = [i for i in range(m * n)]
        self.count = m * n
    def find(self, x):
        if x == self.root[x]:
            return x
        self.root[x] = self.find(self.root[x])
        return self.root[x]
    def union(self, x, y):
        """Merge x to y"""
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x != root_y:
            self.root[root_x] = root_y
            self.count -= 1
    def get_count(self):
        return self.count