leetcode -岛屿数目，RecursionError

Question

我正试图解决莱特码中著名的“岛数”问题。(链接：https://leetcode.com/problems/number-of-islands/)

我使用BFS解决了这个解决方案，但是我得到了以下错误："RecursionError:相对地超过最大递归深度“

我为什么会犯这个错误？我不知道为什么。

这是我的代码：

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"]])

Answer 1

您正在为网格分配int而不是字符串，因此条件会创建无限循环。改变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"]])

Answer 2

您需要添加一些访问矩阵，以确保只在每个单元格中访问一次。

类似这样的东西

visit = [[False ]* 5 ]* 4

def marksZero(grid, i, j):
    if visit[i][j]:
        return
    visit[i][j]=True