当前位置：网站首页>Number of islands

Number of islands

2022-04-23 09:11:00 【Boundless universe PY】

from collections import deque
# Parameters grid It's a 01 matrix
# Return value islands Is the number of islands
class Solution:
def numIslands(self, grid):
if not grid or not grid[0]:
return 0
islands = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j]:
self.bfs(grid, i, j)
islands += 1
return islands
def bfs(self, grid, x, y):
queue = deque([(x, y)])
grid[x][y] = False
while queue:
x, y = queue.popleft()
for delta_x, delta_y in [(1, 0), (0, -1), (-1, 0), (0, 1)]:
next_x = x + delta_x
next_y = y + delta_y
if not self.is_valid(grid, next_x, next_y):
continue
queue.append((next_x, next_y))
grid[next_x][next_y] = False
def is_valid(self, grid, x, y):
n, m = len(grid), len(grid[0])
return 0 <= x < n and 0 <= y < m and grid[x][y]
# The main function
if name == ‘main’:
generator= [
[1,1,1,1,2],
[0,1,0,0,1],
[0,0,0,1,1],
[0,0,0,0,0],
[0,0,0,0,1]
]
solution = Solution()
print(“ Input ：”, generator)
print(“ Output ：”, solution.numIslands(generator))
Insert picture description here

版权声明
本文为[Boundless universe PY]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/04/202204230657123950.html

边栏推荐

猜你喜欢

随机推荐