【代码随想录训练营】【Day 65】【图论-2】| 卡码 99
需强化知识点
- 深度搜索和广度搜索
题目
99. 岛屿数量
思想：遍历到为1的节点，再搜索标记，每遇到新的陆地节点，增加计数
- 深度搜索
- 广度搜索：此处用 [] 作为待遍历队列也可，que（append，popleft）
import collections
def dfs(grid, visited, x, y):
dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]]
for add_x, add_y in dirs:
next_x = x + add_x
next_y = y + add_y
if next_x < 0 or next_x >= len(grid) or next_y < 0 or next_y >= len(grid[0]):
continue
if not visited[next_x][next_y] and grid[next_x][next_y]:
visited[next_x][next_y] = True
dfs(grid, visited, next_x, next_y)
def bfs(grid, visited, x, y):
dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]]
que = collections.deque()
# que = []
que.append([x, y])
visited[x][y] = True
while que:
# cur = que.pop()
cur = que.popleft()
cur_x = cur[0]
cur_y = cur[1]
for add_x, add_y in dirs:
next_x = cur_x + add_x
next_y = cur_y + add_y
if next_x < 0 or next_x >= len(grid) or next_y < 0 or next_y >= len(grid[0]):
continue
if not visited[next_x][next_y] and grid[next_x][next_y]:
que.append([next_x, next_y])
visited[next_x][next_y] = True
tmp = list(map(int, input().split()))
m, n = tmp[0], tmp[1]
grid = [[0]*n for _ in range(m)]
visited = [[False]*n for _ in range(m)]
for i in range(m):
tmp = list(map(int, input().split()))
for j in range(n):
grid[i][j] = tmp[j]
result = 0
for i in range(m):
for j in range(n):
if not visited[i][j] and grid[i][j]:
visited[i][j] = True
result += 1
bfs(grid, visited, i, j)
print(result)