Один вопрос по алгоритму в день — leetcode 200 — количество островов — python

LeetCode
Один вопрос по алгоритму в день — leetcode 200 — количество островов — python

【Название Описание】

【Анализ идей】

Двумерная задача поиска в глубину требует массива посещений, чтобы указать, был ли посещен каждый узел. Обнаруживает все узлы, но начинает поиск в глубину только с узла со значением 1, который еще не был посещен. Причина, по которой эта проблема проста, заключается в том, что это только поиск в глубину, но нет процесса поиска с возвратом.Он заканчивается, когда посещается последний узел, и он не возвращает рекурсивно переменные или значения на верхний уровень.

И временная сложность, и пространственная сложность равны O (длина * ширина).

【Исходный код】

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        length = len(grid)
        if length == 0:
            return 0
        width = len(grid[0])
        self.directions = [[-1, 0], [0, -1], [1, 0], [0, 1]]
        marked = [[0 for _ in range(width)] for _ in range(length)]
        re = 0
        for i in range(length):
            for j in range(width):
                if  marked[i][j]==0 and grid[i][j] == '1':
                    re += 1
                    self.dfs(grid, i, j, length, width, marked)
        return re

    def dfs(self, grid, i, j, length, width, marked):
        marked[i][j] = 1
        for x in range(4):
            x0= i + self.directions[x][0]
            y0= j + self.directions[x][1]
            if 0<=x0<length and 0<=y0<width and marked[x0][y0]==0 and grid[x0][y0]=='1':
                self.dfs(grid, x0, y0, length, width, marked)
Категории