递归解法求解网格未被守卫监控单元格数问题排查

这是一道LeetCode半热门题目，我不想直接抄网上的解法，而是想通过自己解决来掌握递归。现在我的代码总是出现调用栈溢出，想问问问题出在哪，求反馈。

题目描述 #

给定两个整数m和n，表示一个0索引的m×n网格。同时给定两个二维整数数组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"

当前代码 #

from typing import List

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

问题根源：递归逻辑错误导致无限循环 #

你的DFS逻辑完全不符合题目中守卫的视野规则，且未处理重复访问问题，直接引发栈溢出：

• 错误的遍历逻辑：题目中守卫是沿四个方向直线观测，遇墙或守卫即停止，但你的DFS是向四个方向同时递归，相当于遍历所有无墙区域，完全违背规则。
• 无重复访问限制：标记单元格为'1'后，未在递归判断条件中排除该状态，导致递归在已标记单元格间来回调用（如A→B、B→A），无限循环直至栈溢出。
• 忽略守卫阻挡：未将'G'（守卫）加入终止条件，会把守卫位置标记为'1'，还会穿过守卫继续递归，不符合题目要求。

修复后的递归思路 #

对每个守卫，沿四个方向直线递归，遇边界、墙或守卫立即停止：

1. 给DFS增加方向参数，每次仅沿一个方向递归；
2. 终止条件加入'G'和已标记状态'1'的判断；
3. 单向递归不回头，避免重复调用。

修复后的代码 #

from typing import List

def countUnguarded(m: int, n: int, guards: List[List[int]], walls: List[List[int]]) -> int:
    def dfs(grid, row, col, dr, dc):
        # 终止条件：越界、遇到墙、遇到守卫
        if row < 0 or row >= m or col < 0 or col >= n or grid[row][col] in ('W', 'G'):
            return
        # 标记为已监控
        grid[row][col] = '1'
        # 沿当前方向继续递归
        dfs(grid, row + dr, col + dc, dr, dc)

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

    # 标记守卫位置
    for r, c in guards:
        grid[r][c] = 'G'
    # 标记墙的位置
    for r, c in walls:
        grid[r][c] = 'W'

    # 对每个守卫，向四个方向启动DFS
    directions = [(1,0), (-1,0), (0,1), (0,-1)]
    for r, c in guards:
        for dr, dc in directions:
            dfs(grid, r + dr, c + dc, dr, dc)

    # 统计未被监控且未被占据的单元格
    count = 0
    for row in grid:
        count += row.count('0')
    return count

修复说明 #

• 每个守卫的四个方向分别启动DFS，每次递归仅沿单一方向推进，遇阻挡则停止；
• 终止条件明确包含'G'，避免穿过守卫；
• 单向递归不会出现来回调用，彻底解决栈溢出问题；
• 从守卫的下一个单元格开始递归，保留守卫本身的'G'标记。

内容的提问来源于stack exchange，提问作者Duck Dodgers