Подсчет островов – почему мой код не работает? [closed]

Пытаюсь решить классический подсчет островов в матричной задаче. Учитывая двумерную сеточную карту, состоящую из единиц (земля) и нулей (вода), я должен рассчитать количество островов.

Остров окружен водой и образован соединением соседних земель по горизонтали или вертикали. Вот мое решение 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

0

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *