基于BFS的二维数组指定路径查找：代码修正求助

原DFS实现的常见问题 #

• 访问标记回溯错误：未在递归退出时恢复单元格访问状态，导致后续路径被错误阻断
• 计数逻辑不严谨：到达终点时未严格校验已收集的2的数量是否恰好为4
• 边界与障碍物判断遗漏：越界或碰到1时未及时终止递归
• 对2的处理有误：已收集够4个2后仍允许继续访问其他2，违反不可重复访问规则

修正后的DFS实现方案 #

核心思路 #

1. 回溯式访问标记：直接修改原网格标记已访问单元格，递归退出时恢复原值，避免额外空间开销
2. 精准状态传递：递归时携带当前已收集的2的数量，严格控制路径中2的总数
3. 严格终止条件：
   • 越界/碰到障碍物1：直接终止
   • 到达终点3：仅当已收集2的数量为4时，才计入有效路径
   • 碰到2：若已收集满4个，直接终止当前分支；否则计数+1并标记访问

代码示例（Python） #

def count_valid_paths(grid):
    rows, cols = len(grid), len(grid[0]) if grid else 0
    start_x, start_y = 0, 0
    end_x, end_y = rows - 1, cols - 1

    # 提前校验起点终点合法性
    if grid[start_x][start_y] == 1 or grid[end_x][end_y] == 1:
        return 0

    valid_count = 0
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    def dfs(x, y, collected):
        nonlocal valid_count
        # 越界、障碍物或已访问（已被标记为1）
        if x < 0 or x >= rows or y < 0 or y >= cols or grid[x][y] == 1:
            return
        # 到达终点，校验2的数量
        if x == end_x and y == end_y:
            if collected == 4:
                valid_count += 1
            return

        current_val = grid[x][y]
        new_collected = collected
        # 处理当前单元格为2的情况
        if current_val == 2:
            if collected >= 4:
                return  # 已收集够4个2，无法再走该单元格
            new_collected = collected + 1

        # 标记为已访问（临时改为1）
        grid[x][y] = 1
        # 遍历四个方向
        for dx, dy in directions:
            dfs(x + dx, y + dy, new_collected)
        # 回溯，恢复原单元格值
        grid[x][y] = current_val

    dfs(start_x, start_y, 0)
    return valid_count

关键优化点 #

• 提前剪枝：若网格中2的总数不足4，可直接返回0，减少无效递归
• 访问标记复用：利用原网格修改实现访问标记，无需额外开辟访问矩阵
• 分支截断：已收集满4个2时，碰到其他2直接终止该分支，避免无效路径探索

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