题解 | #岛屿数量#python实现

1. BFS方法：借用一个队列 queue,实现BFS。
   判断队列首部节点 (i, j) 是否未越界且为 1：

class Solution:
    def solve(self , grid ):
        # write code here
        def BFS(grid,i,j):
            queue = [[i,j]]
            while queue:#直到队列为空，搜索结束。
                #循环pop 队列首节点，直到整个队列为空，此时已经遍历完此岛屿。
                [i,j] = queue.pop(0)
                # 如果一个位置为 1，则将其加入队列，开始进行广度优先搜索。
                if 0 <= i <len(grid) and 0 <= j <len(grid[0]) and grid[i][j] == '1':
                    #在广度优先搜索的过程中，每个搜索到的 11 都会被重新标记为 0。
                    grid[i][j] = '0'
                    #（删除岛屿节点），并将此节点上下左右节点 (i+1,j),(i-1,j),(i,j+1),(i,j-1) 加入队列； 若不是则跳过此节点； 
                    queue += [[i - 1,j] , [i + 1, j],[i,j - 1],[i, j + 1]]
        count = 0
         #为了求出岛屿的数量，我们可以扫描整个二维网格。
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '0':continue 
                BFS(grid, i, j)
                count += 1
        return count

2、DFS解决：

每走过一个陆地格子，就把格子的值改为 2，这样当我们遇到 2 的时候，就知道这是遍历过的格子了。
0 —— 海洋格子
1 —— 陆地格子（未遍历过）
2 —— 陆地格子（已遍历过）

如果遍历过的陆地取0，这样我们就无法区分「海洋格子」和「已遍历过的陆地格子」了。如果题目更复杂一点，这很容易出 bug。

class Solution:
    def solve(self , grid ):
        # write code here
        def dfs(grid, i, j):
            #判断 base case
            #如果这个格子不是岛屿，直接返回
            if not 0 <= i < len(grid) or not 0 <= j < len(grid[0]) or grid[i][j] != '1': return
            grid[i][j] = '2'
            #访问上、下、左、右四个相邻结点
            dfs(grid, i + 1, j)
            dfs(grid, i, j + 1)
            dfs(grid, i - 1, j)
            dfs(grid, i, j - 1)
        count = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                #判断坐标 (i, j) 是否在
                if grid[i][j] == '1':
                    dfs(grid, i, j)
                    count += 1
        return count