Пытаюсь решить классический подсчет островов в матричной задаче. Учитывая двумерную сеточную карту, состоящую из единиц (земля) и нулей (вода), я должен рассчитать количество островов.
Остров окружен водой и образован соединением соседних земель по горизонтали или вертикали. Вот мое решение BFS [time complexity O(mn), space complexity O(n+m)] — почему отсутствуют острова? Как мне сделать это чище?
from collections import deque
def get_steps(i, j, m, n):
if i > 0:
yield i-1, j
if j > 0:
yield i, j-1
if i+1 < m:
yield i+1, j
if j+1 < n:
yield i, j+1
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
seen = set()
c = 0
for i in range(m:=len(grid)):
for j in range(n:=len(grid[0])):
if (i, j) in seen:
continue
seen.add((i, j))
if grid[i][j] == "1":
c += 1
queue = deque([(i, j)])
while queue:
i, j = queue.popleft()
for ni, nj in get_steps(i, j, m, n):
if (ni, nj) not in seen:
seen.add((ni, nj))
if grid[ni][nj] == "1":
queue.append((ni, nj))
return c