200. 岛屿数量
扫描整个二维网格。如果一个位置为1,则以其为起始节点开始进行深度优先搜索。在深度优先搜索的过程中,每个搜索到的1都会被重新标记为0。最终岛屿的数量就是我们进行深度优先搜索的次数。
看下代码,怎么实现广度优先遍历,和二叉树广度优先遍历有什么区别,如何使用deque:
from collections import deque
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
lielen = len(grid)
if lielen==0:
return 0
hanglen = len(grid[0])
ans = 0
for i in range(lielen):
for j in range(hanglen):
if grid[i][j]=="1":
grid[i][j] = "0"
ans += 1
# 利用这个队列deque来进行广度优先遍历
# 注意,这里和二叉树里的层序遍历是相似的,但是不需要区分层数
queue = deque([(i,j)])
while queue:
row, col = queue.popleft()
for x, y in [(row - 1, col), (row + 1, col), (row, col - 1), (row, col + 1)]:
if 0 <= x < lielen and 0 <= y < hanglen and grid[x][y] == "1":
queue.append((x, y))
grid[x][y] = "0"
return ans