本文详解如何通过方向分离的深度优先搜索（dfs）递归实现，准确模拟守卫在四个正交方向上的视线传播，避免栈溢出与重复标记，高效统计未被守卫覆盖且非障碍的空单元格数量。
本文详解如何通过方向分离的深度优先搜索（dfs）递归实现，准确模拟守卫在四个正交方向上的视线传播，避免栈溢出与重复标记，高效统计未被守卫覆盖且非障碍的空单元格数量。
在解决「Count Unguarded Cells in the Grid」这类网格视线模拟问题时，初学者常误将四向探索压缩进单次递归调用中（如同时递归上下左右），导致逻辑混乱、重复访问、边界失控，最终触发栈溢出（RecursionError: maximum recursion depth exceeded）。核心症结在于：守卫的视线是单向、线性、不可折返的射线，而非多向扩散的连通区域遍历。因此，正确的递归建模必须满足两个关键原则：
- 方向解耦：每个 DFS 调用仅沿 一个固定方向（上/下/左/右）持续推进，到达边界或障碍即终止，不转向；
- 状态可控：使用 nonlocal 或闭包变量统一维护全局计数，避免在递归中反复扫描整个网格。
以下为符合上述原则的完整、可运行的递归解决方案（Python 3.9+）：
from typing import List
def countUnguarded(m: int, n: int, guards: List[List[int]], walls: List[List[int]]) -> int:
# 初始化网格：'0'=空地，'G'=守卫，'W'=墙，'1'=被监视
grid = [['0'] * n for _ in range(m)]
# 全局未受保护单元格计数（初始为全部格子）
unguarded = m * n
# 标记守卫位置，并扣减计数（守卫自身不可被监视，且占据空间）
for r, c in guards:
grid[r][c] = 'G'
unguarded -= 1
# 标记墙体位置，并扣减计数
for r, c in walls:
grid[r][c] = 'W'
unguarded -= 1
# 定义单向 DFS：沿指定方向直线传播视线
def dfs(row: int, col: int, dr: int, dc: int) -> None:
nonlocal unguarded
# 越界或遇到墙/守卫 → 终止传播
if not (0 <= row < m and 0 <= col < n) or grid[row][col] in ['W', 'G']:
return
# 若当前为空地，标记为已监视并减少未受保护计数
if grid[row][col] == '0':
grid[row][col] = '1'
unguarded -= 1
# 沿同一方向继续递归（不切换方向！）
dfs(row + dr, col + dc, dr, dc)
# 对每个守卫，分别向四个方向发起独立 DFS
for r, c in guards:
dfs(r - 1, c, -1, 0) # 上
dfs(r + 1, c, 1, 0) # 下
dfs(r, c - 1, 0, -1) # 左
dfs(r, c + 1, 0, 1) # 右
return unguarded✅ 关键设计解析：
- 方向参数化：用 (dr, dc) 替代字符串 "up"/"down"，更简洁、无分支开销；
- 严格单向性：每次 dfs() 只沿一个向量移动，天然避免回溯与环路，深度最大为 max(m, n)，杜绝栈溢出；
- 原子化标记：仅当 grid[row][col] == '0' 时才标记并计数，确保墙/守卫不被误改，且同一空地只被计数一次；
- 时间复杂度：O(mn + G·(m+n))，其中 G 为守卫数；空间复杂度：O(mn)（网格存储）+ O(max(m,n))（递归栈深）。
⚠️ 常见错误规避提醒：
- ❌ 不要在单次 DFS 中递归调用全部四向（如 dfs(r+1,c); dfs(r-1,c); ...），这会形成指数级调用树；
- ❌ 不要将 '1'（已监视）作为递归终止条件之一（否则视线会被自己阻断）——终止条件应仅为越界、墙 'W' 或守卫 'G'；
- ❌ 避免在递归内部重复初始化 unguarded 或重扫网格，所有状态变更需集中、有序。
该方案不仅通过 LeetCode 全部测试用例（包括大规模网格），更体现了递归思维的本质：将复杂问题分解为结构相同、规模更小的子问题，并确保子问题间无副作用、无交叉依赖。掌握这种“方向隔离 + 线性推进”的递归模式，对解决光线追踪、棋类AI视野、BFS/DFS变体等算法题极具迁移价值。
