Блог

Главная - Вопросы по программированию - Рекурсивное решение для числа островов

Рекурсивное решение для числа островов

#python #algorithm

#python #алгоритм

Вопрос:

Я пытаюсь решить проблему количества островов — LeetCode

Учитывая 2d-сеточную карту '1' s (суша) и '0' s (вода), подсчитайте количество островов. Остров окружен водой и образуется путем соединения соседних земель по горизонтали или вертикали. Вы можете предположить, что все четыре ребра сетки окружены водой.

Пример 1:

 Input:
11110
11010
11000
00000

Output: 1

Пример 2:

 Input:
11000
11000
00100
00011

Output: 3

Принятое решение:

 #Recursively solution 
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid:
            return 0
        step = 0
        r, c = len(grid), len(grid[0])
        visited = [[False for _ in range(c)] for _ in range(r)]
        for i in range(r):
            for j in range(c):
                if grid[i][j] == "1" and not visited[i][j]:
                    step  = 1
                    self.dfs(grid, i, j, visited)
        return step

    def dfs(self, grid, i, j, visited):
        if i<0 or j<0 or i>=len(grid) or j>=len(grid[0]) or grid[i][j] != '1' or visited[i][j]:        
            return 
        visited[i][j] = True
        self.dfs(grid, i 1, j, visited)
        self.dfs(grid, i-1, j, visited)
        self.dfs(grid, i, j 1, visited)
        self.dfs(grid, i, j-1, visited)

В решении использовалась смесь рекурсии и итерации.

Как можно решить проблему исключительно с помощью рекурсии?

Комментарии:

1. просто из любопытства я спрашиваю. почему вы хотите, чтобы он был рекурсивным, если он работает итеративно?

2. Технически вместо итерации по карте вы можете выполнить DFS поверх нее, но стек вызовов, вероятно, будет слишком большим. Idk, если есть ограничение на это.

3. потому что я практикую рекурсию @AlbinPaul

Ответ №1:

Ну, все, что вам нужно сделать, это изменить цикл на рекурсивную функцию, которая переходит от некоторой координаты (r, c) к следующей координате (r, c 1) или (r 1,0) при достижении конца строки.

Пример кода:

 def numIslands(grid, row, col):
    if not grid: return 0

    ans = 0

    if grid[row][col]==1:
        ans =1
        dfs(grid,row,col)

    col =1
    if col == len(grid[0]):
        col=0
        row =1

    if row == len(grid):
        return ans

    return ans   numIslands(grid, row, col)

def dfs(grid, i, j):
    if i<0 or j<0 or i>=len(grid) or j>=len(grid[0]) or grid[i][j] != 1:        
        return 
    grid[i][j] = -1
    dfs(grid, i 1, j)
    dfs(grid, i-1, j)
    dfs(grid, i, j 1)
    dfs(grid, i, j-1)


print(numIslands([
[1,1,0,0,0],
[1,1,0,0,0],
[0,0,1,0,0],
[0,0,0,1,1]
],0,0))
Метки: