H5W3
当前位置:H5W3 > python > 正文

【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

本文地址:H5W3 » 【Python】leetcode岛屿数量(200)-BFS

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址