岛屿数量

1、题目

图1

2、题解

广度优先搜索

通过扫描整个二维网络，如果某个位置为1，则将其加入队列，进行BFS。在BFS中，每搜索到一个1都会重新被标记为0.直到队列为空，搜索结束。最终岛屿数量为进行BFS的次数。

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        s_r = len(grid)
        if s_r == 0:
            return 0
        s_c = len(grid[0])

        island_num = 0

        for r in range(s_r):
            for c in range(s_c):
                if grid[r][c] == "1":
                    island_num += 1
                    grid[r][c] = "0"
                    que = [(r,c)]
                    while que:
                        row,col = que.pop()
                        for x,y in [(row-1,col),(row+1,col),(row,col-1),(row,col+1)]:
                            if 0<=x<s_r and 0<=y<s_c and grid[x][y] == "1":
                                que.append((x,y))
                                grid[x][y] = "0"
            
        return island_num