【Python】leetcode岛屿数量(200)-BFS

leetcode岛屿数量(200)-BFS

一闪一闪发布于 28 分钟前

给你一个由 '1'(陆地)和 '0'(水)组成的的二维网格,请你计算网格中岛屿的数量。
岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外,你可以假设该网格的四条边均被水包围。
 
示例 1:

输入:grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
输出:1

Class Solution:

def numIslands(self, grid):

count=0

for row in range(len(grid)):

for col in range(len(grid[0])):

if grid[row][col]=='1': # 发现第一个陆地

count+=1 # 直接加1,周围其他的一会再后面被标记掉,不会导致总数增加

grid[row][col]='0' # 计入后就标记掉

land_positions=collections.deque() # 声明一个队列开始进行标准BFS 广度优先算法

land_positions.append([row,col]) #把位置作为队列值加入队列

while len(land_positions>0):# 只要队列中还有值就继续执行

x,y =land_positions.popleft() # 取出队列的队首,也就是最先进入的值

for new_x,new_y in [[x,y+1],[x,y-1],[x+1,y],[x-1,y]]:# 查看陆地四周的位置

if 0<=new_x<len(grid) and 0<new_y<len(grid[0]) and grid[new_x][new_y]=='1': #这些位置如果在整个数组中,并且为‘1’那么就是同一片陆地

grid[new_x][new_y]='0' # 将同一片陆地标记掉

land_positions.append([new_x, new_y]) #如果是陆地,它的周边还需要继续挖掘,因此加入队列中

return count

python队列leetcodebfs

阅读 24发布于 28 分钟前

本作品系原创,采用《署名-非商业性使用-禁止演绎 4.0 国际》许可协议

avatar

一闪一闪

7 声望

1 粉丝

0 条评论

得票时间

avatar

一闪一闪

7 声望

1 粉丝

宣传栏

给你一个由 '1'(陆地)和 '0'(水)组成的的二维网格,请你计算网格中岛屿的数量。
岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外,你可以假设该网格的四条边均被水包围。
 
示例 1:

输入:grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
输出:1

Class Solution:

def numIslands(self, grid):

count=0

for row in range(len(grid)):

for col in range(len(grid[0])):

if grid[row][col]=='1': # 发现第一个陆地

count+=1 # 直接加1,周围其他的一会再后面被标记掉,不会导致总数增加

grid[row][col]='0' # 计入后就标记掉

land_positions=collections.deque() # 声明一个队列开始进行标准BFS 广度优先算法

land_positions.append([row,col]) #把位置作为队列值加入队列

while len(land_positions>0):# 只要队列中还有值就继续执行

x,y =land_positions.popleft() # 取出队列的队首,也就是最先进入的值

for new_x,new_y in [[x,y+1],[x,y-1],[x+1,y],[x-1,y]]:# 查看陆地四周的位置

if 0<=new_x<len(grid) and 0<new_y<len(grid[0]) and grid[new_x][new_y]=='1': #这些位置如果在整个数组中,并且为‘1’那么就是同一片陆地

grid[new_x][new_y]='0' # 将同一片陆地标记掉

land_positions.append([new_x, new_y]) #如果是陆地,它的周边还需要继续挖掘,因此加入队列中

return count

以上是 【Python】leetcode岛屿数量(200)-BFS 的全部内容, 来源链接: www.h5w3.com/113843.html

度小满广告!风险提示:广告信息均来自平台方,不代表平台安全性,不构成建议!
度小满
回到顶部