给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
示例 ：
输入：grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
输出：3
广度优先搜索和深度优先搜索，是全部遍历图的算法，关键在于优先的方式不同，即遍历的方式不同。pivot。
广度优先搜索，常用保存每一层的值，然后弹出这一层的每一个值，搜索下一层的值，加入队列。由于队列是
，所以是一层一层的搜索。
bfs.gif
# 广度优先搜索
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
# 网格的行数
nr = len(grid)
if nr == 0:
return 0
# 网格的列数
nc = len(grid[0])
# 岛屿的个数
num_islands = 0
# 遍历每一格
for r in range(nr):
for c in range(nc):
# 如果是陆地
if grid[r][c] == "1":
num_islands += 1
grid[r][c] = "0"
# 双向队列，可在队列头部和尾部添加、删除元素
neighbors = collections.deque([(r, c)])
# 如果队列有值
while neighbors:
# 弹出最左边的（即最先进入的），弹出后就不再考虑了
row, col = neighbors.popleft()
# 搜索最先进入的左、右、上、下 4个方向的格子
for x, y in [(row - 1, col), (row + 1, col), (row, col - 1), (row, col + 1)]:
# 如果是陆地，加入队列，准备下次搜索左右上下
if 0 <= x < nr and 0 <= y < nc and grid[x][y] == "1":
neighbors.append((x, y))
grid[x][y] = "0"
return num_islands
