'leetcode - number of islands, RecursionError
I'm trying to solve the famous problem of "number of islands" from leetcode. (link : https://leetcode.com/problems/number-of-islands/)
I solved this solution using BFS, but I got this error : "RecursionError: maximum recursion depth exceeded in comparison"
Why I get this error? I cant figure why.
Here is my code:
def numIslands(grid):
islands = 0
for i in range(0, len(grid)):
for j in range(0, len(grid[0])):
if(grid[i][j] == "1"):
islands += 1
marksZero(grid, i, j)
print(islands)
return islands
def marksZero(grid, i, j):
if(grid[i][j] == "0"):
return
grid[i][j] = 0
if(i - 1 >= 0):
marksZero(grid, i - 1, j)
if(i + 1 < len(grid)):
marksZero(grid, i + 1, j)
if(j - 1 >= 0):
marksZero(grid, i, j - 1)
if(j + 1 < len(grid[0])):
marksZero(grid, i, j + 1)
numIslands([["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]])
Solution 1:[1]
You are assigning int instead of string to your grid,therefore condition creates infinite loop.
Change grid[i][j] = "0"
def numIslands(grid):
islands = 0
for i in range(0, len(grid)):
for j in range(0, len(grid[0])):
if(grid[i][j] == "1"):
islands += 1
marksZero(grid, i, j)
print(islands)
return islands
def marksZero(grid, i, j):
if(grid[i][j] == "0"):
return
grid[i][j] = "0"
if(i - 1 >= 0):
marksZero(grid, i - 1, j)
if(i + 1 < len(grid)):
marksZero(grid, i + 1, j)
if(j - 1 >= 0):
marksZero(grid, i, j - 1)
if(j + 1 < len(grid[0])):
marksZero(grid, i, j + 1)
numIslands([["1", "1", "1", "1", "0"],
["1", "1", "0", "1", "0"],
["1", "1", "0", "0", "0"],
["0", "0", "0", "0", "0"]])
Solution 2:[2]
you need to add some visit matrix to make sure you are in each cell only once
something like that
visit = [[False ]* 5 ]* 4
def marksZero(grid, i, j):
if visit[i][j]:
return
visit[i][j]=True
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|---|
| Solution 1 | Tomáš Šturm |
| Solution 2 | Gilad Fuchs |