LeetCode-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’

解题思路一：bfs，主要思想都是遇到一个没有visited过的"陆地"先result += 1，然后用深搜或者广搜将这片"陆地"全部做上visited标记。

class Solution:
    def __init__(self):
        self.dirs = [(-1,0), (0, 1), (1, 0), (0, -1)] # 左上右下
    def numIslands(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])
        visited = [[False] * n for _ in range(m)]
        result = 0
        for i in range(m):
            for j in range(n):
                if not visited[i][j] and grid[i][j] == '1':
                    result += 1
                    self.bfs(grid, i, j, visited)
        return result

    def bfs(self, grid, x, y, visited):
        q = deque()
        q.append((x, y))
        visited[x][y] = True
        while q:
            x, y = q.popleft()
            for d in self.dirs:
                nextx = x + d[0]
                nexty = y + d[1]
                if nextx < 0 or nextx >= len(grid) or nexty < 0 or nexty >= len(grid[0]):
                    continue
                if not visited[nextx][nexty] and grid[nextx][nexty] == '1':
                    q.append((nextx, nexty))
                    visited[nextx][nexty] = True

时间复杂度：O(nm)
空间复杂度：O(nm)

解题思路二：dfs

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])
        visited = [[False] * n for _ in range(m)]
        dirs = [(-1,0), (0, 1), (1, 0), (0, -1)] # 左上右下
        result = 0
        def dfs(x, y):
            for d in dirs:
                nextx = x + d[0]
                nexty = y + d[1]
                if nextx < 0 or nextx >= m or nexty < 0 or nexty >= n:
                    continue
                if not visited[nextx][nexty] and grid[nextx][nexty] == '1':
                    visited[nextx][nexty] = True
                    dfs(nextx, nexty)

        for i in range(m):
            for j in range(n):
                if not visited[i][j] and grid[i][j] == '1':
                    visited[i][j] = True
                    result += 1
                    dfs(i, j)
        return result

时间复杂度：O(nm)
空间复杂度：O(nm)

解题思路三：并查集

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        f = {}

        def find(x):
            f.setdefault(x, x)
            if f[x] != x:
                f[x] = find(f[x])
            return f[x]

        def union(x, y):
            f[find(x)] = find(y)

        if not grid: return 0
        row = len(grid)
        col = len(grid[0])

        for i in range(row):
            for j in range(col):
                if grid[i][j] == "1":
                    for x, y in [[-1, 0], [0, -1]]:
                        tmp_i = i + x
                        tmp_j = j + y
                        if 0 <= tmp_i < row and 0 <= tmp_j < col and grid[tmp_i][tmp_j] == "1":
                            union(tmp_i * row + tmp_j, i * row + j)
        # print(f)
        res = set()
        for i in range(row):
            for j in range(col):
                if grid[i][j] == "1":
                    res.add(find((i * row + j)))
        return len(res)

时间复杂度：O(mn)
空间复杂度：O(nm)