队列-广度遍历-岛屿计算

题目： 岛屿计算

给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。

解题思路：

首先明白岛屿的定义：一块 1 周围全是 0，即为一个岛屿。（注意：grid 数组内的 1、0 均为char型字符，非整型）

示例1 中所有 1 都可以连接到一起，即所有 1 组成一个岛屿。示例2 中的三个岛屿：左上角四个1、中间一个1、右下角一个一，分别组成三个岛屿。

Flood fill算法是从一个区域中提取若干个连通的点与其他相邻区域区分开（或分别染成不同颜色）的经典算法。因为其思路类似洪水从一个区域扩散到所有能到达的区域而得名。在 GNU Go 和 扫雷 中，Flood Fill算法被用来计算需要被清除的区域。由上述定义可看出该题是典型的Flood fill算法类型例题，将岛屿与水分开，并染成特定颜色，以记录已累加过该岛屿。

每块岛屿可以看成相连的一个个节点，只需把所有相连节点遍历殆尽并标上特殊值以记录该节点已访问过，则遍历殆尽时证明一块岛屿已找到。

方法一： 广度优先

class Solution:


    def numIslands(self, grid: list) -> int:
        if not grid or len(grid) == 0:
            return 0
        row, colum = len(grid), len(grid[0])
        # 岛屿计数
        island_num = 0
        for i in range(row):
            for j in range(colum):
                if grid[i][j] == '1':
                    self.bfs(grid, i, j, row, colum)
                    # 遍历一次计数加一，直到结束
                    island_num += 1
        return island_num

    def bfs(self, grid: list, i: int, j:int, row: int, colum: int):
        queue = list()
        queue.append((i, j))
        while queue:
            a, b = queue.pop(0)
            # 上方判断
            if a - 1 >= 0 and grid[a - 1][b] == '1':
                queue.append((a - 1, b))
                grid[a - 1][b] = '0'
            # 下方判断
            if a + 1 < row and grid[a + 1][b] == '1':
                queue.append((a + 1, b))
                grid[a + 1][b] = '0'
            # 左边判断
            if b - 1 >= 0 and grid[a][b - 1] == '1':
                queue.append((a, b - 1))
                grid[a][b - 1] = '0'
            # 右边判断
            if b + 1 < colum and grid[a][b + 1] == '1':
                queue.append((a, b + 1))
                grid[a][b + 1] = '0'


if __name__ == '__main__':

    grid = [
        ["1", "1", "0", "0", "1"],
        ["1", "1", "0", "1", "0"],
        ["0", "0", "1", "0", "0"],
        ["1", "0", "0", "1", "1"]
    ]
    S = Solution()
    num = S.numIslands(grid)
    print(num)
>>> 6

方法二：深度优先

class Solution:


    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid or len(grid) == 'o': return 0
        row, columns = len(grid), len(grid[0])
        count = 0
        for i in range(row):
            for j in range(columns):
                if grid[i][j] == '1':
                    self.dfs(grid, i, j, row, columns)
                    count += 1
        return count

    def dfs(self, grid: List[List[str]], i: int, j: int, row: int, columns: int):
        if i >= row or i < 0 or j >= columns or j < 0 or grid[i][j] == '0': return
        grid[i][j] = '0'
        self.dfs(grid, i - 1, j, row, columns)
        self.dfs(grid, i, j - 1, row, columns)
        self.dfs(grid, i + 1, j, row, columns)
        self.dfs(grid, i, j + 1, row, columns)

···