#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))