张家界做旅游网站,seo网站建设技巧,株洲网站建设联系方式,建设网站语言选择【代码随想录训练营】【Day 65】【图论-2】| 卡码 99
需强化知识点
深度搜索和广度搜索
题目
99. 岛屿数量
思想#xff1a;遍历到为1的节点#xff0c;再搜索标记#xff0c;每遇到新的陆地节点#xff0c;增加计数
深度搜索广度搜索#xff1a;此处用 [] 作为待遍…【代码随想录训练营】【Day 65】【图论-2】| 卡码 99
需强化知识点
深度搜索和广度搜索
题目
99. 岛屿数量
思想遍历到为1的节点再搜索标记每遇到新的陆地节点增加计数
深度搜索广度搜索此处用 [] 作为待遍历队列也可queappendpopleft
import collectionsdef 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_xnext_y y add_yif next_x 0 or next_x len(grid) or next_y 0 or next_y len(grid[0]):continueif not visited[next_x][next_y] and grid[next_x][next_y]:visited[next_x][next_y] Truedfs(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] Truewhile 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_xnext_y cur_y add_yif next_x 0 or next_x len(grid) or next_y 0 or next_y len(grid[0]):continueif not visited[next_x][next_y] and grid[next_x][next_y]:que.append([next_x, next_y])visited[next_x][next_y] Truetmp 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] Trueresult 1bfs(grid, visited, i, j)print(result)
