计算网格中不受保护的单元格（递归）

Question

这是一个半流行的leetcode问题。我知道网上有很多解决方案，但我正在通过自己解决所有这些问题来练习，以真正掌握递归。我想知道我目前的方法有什么问题；我一直在最大化调用堆栈。我将不胜感激！问题是这样的：

“给定两个整数 m 和 n，表示 0 索引的 m x n 网格。还给定两个 2D 整数数组 Guards 和 Walls，其中 Guards[i] = [rowi, coli] 和 Walls[j] = [rowj, colj ] 分别代表第 i 个守卫和第 j 个墙的位置。

守卫可以从他们的位置开始看到四个基本方向（北、东、南或西）的每个牢房，除非被墙壁或其他守卫阻挡。如果至少有一名警卫可以看到某个牢房，则该牢房被看守。

返回未被保护的未占用单元格的数量。

示例

输入：

m = 4, n = 6, guards = [[0,0],[1,1],[2,3]], walls = [[0,1],[2,2],[1,4]]

输出：

 "7"

这是我到目前为止编写的代码：

def countUnguarded(m: int, n: int, guards: List[List[int]], walls: List[List[int]]) -> int:
    def dfs(grid, row, col):
        if row < 0 or row >= m or col < 0 or col >= n or grid[row][col] == 'W':            
            return

        # Mark cell as watched
        print("marking")
        grid[row][col] = '1'

        # Recursive call
        dfs(grid, row + 1, col)
        dfs(grid, row - 1, col)
        dfs(grid, row, col + 1)
        dfs(grid, row, col - 1)

    grid = [['0'] * n for _ in range(m)]

    # Update grid to mark guards as 'G'
    for guard in guards:
        row, col = guard
        grid[row][col] = 'G'

    # Update grid to mark walls as 'W'
    for wall in walls:
        row, col = wall
        grid[row][col] = 'W'

    # Run dfs for each cell with Guard
    for row in range(m):
        for col in range(n):
            if grid[row][col] == 'G':
                print(f"running DFS at point {row, col}")
                dfs(grid, row, col)                

    # count result
    unguarded_count = 0
    for row in range(m):
        for col in range(n):
            if grid[row][col] == '0':
                unguarded_count += 1

    return unguarded_count

Answer 1

这段代码就是问题所在：

# Recursive call
dfs(grid, row + 1, col)
dfs(grid, row - 1, col)

在主函数第一次调用时，dfs 被调用时 row=0。

然后 dfs 使用 row + 1（值 1）调用自身

然后 dfs 使用 row + 1（值 2）调用自身

然后 dfs 使用 row + 1（值 3）调用自身

然后 dfs 使用 row + 1 调用自身（值 4 超出范围，因此该调用立即退出）

然后 dfs 使用 row - 1（值 2）调用自身

然后 dfs 使用 row + 1（值 3）调用自身

然后 dfs 使用 row + 1 调用自身（值 4 超出范围，因此该调用立即退出）

然后 dfs 使用 row - 1（值 2）调用自身

...等等等等。 row 只是在 2,3,4,2,3,4,2,3,4.... 永远循环。