CSES问题集GridPaths：DFS迷宫遍历程序路径数统计异常求助

核心错误：方向映射完全颠倒 #

你的turn数组与移动指令的对应关系完全错误，导致程序执行的移动方向和预期不符，这是路径计数错误的根源：

• 你定义的turn[0] = {0,-1}对应'U'，但实际这个方向是向左（y轴减1），而非向上；
• turn[1] = {1,0}对应'R'，实际是向下（x轴加1），而非向右；
• turn[2] = {0,1}对应'D'，实际是向右（y轴加1），而非向下；
• turn[3] = {-1,0}对应'L'，实际是向上（x轴减1），而非向左。

正确的方向映射应该是：

// 对应顺序：U(上), R(右), D(下), L(左)
pair<int,int> turn[4] = {{-1,0}, {0,1}, {1,0}, {0,-1}};

其他问题与优化点 #

1. 替换map为数组，避免默认值陷阱
   使用std::map存储指令会带来不必要的性能开销，而且当访问未初始化的键时，map会自动插入默认值0（对应错误的方向）。改用固定大小的数组更安全高效：

   int dirs[48]; // 题目输入固定为48个字符
   

   在main函数中初始化：

   memset(dirs, -1, sizeof(dirs)); // 先默认设为-1（通配符）
   for(int i=0;i<s.size();i++){
       if(s[i]=='U') dirs[i] = 0;
       else if(s[i]=='R') dirs[i] = 1;
       else if(s[i]=='D') dirs[i] = 2;
       else if(s[i]=='L') dirs[i] = 3;
       // '?'保持-1即可
   }
   

   然后在dfs中直接访问dirs[deep]。

2. 添加提前剪枝，提升效率
   7x7网格的DFS如果不剪枝，会产生大量无效递归，即使结果正确也可能超时。可以添加以下剪枝条件：

   • 若当前位置到终点的曼哈顿距离 > 剩余步数（48 - deep），直接返回（不可能到达终点）；
   • 剩余步数减去曼哈顿距离必须是偶数，否则无法通过绕路到达终点。

   剪枝代码示例：

   // 在dfs开头，终点是(6,0)
   int remaining = 48 - deep;
   int dist = abs(x - 6) + abs(y - 0);
   if(dist > remaining || (remaining - dist) % 2 != 0){
       return;
   }
   

3. 添加当前位置访问检查
   在dfs函数开头，添加对当前位置是否已被访问的检查，避免因逻辑错误导致的重复访问：

   if(graph[x][y] == 1){
       return;
   }
   

4. 优化全局变量使用
   全局变量counts和graph虽然可以工作，但改为通过函数参数传递更安全，避免全局变量带来的潜在冲突：

   void dfs(int x,int y,int deep, int& counts, int graph[7][7], int dirs[48]){
       // ... 函数内容 ...
   }
   

修正后的完整代码示例 #

#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;

// 方向：U(上), R(右), D(下), L(左)
pair<int,int> turn[4] = {{-1,0}, {0,1}, {1,0}, {0,-1}};

void dfs(int x,int y,int deep, int& counts, int graph[7][7], int dirs[48]){
    // 到达终点且步数正确
    if(x==6 && y==0){
        if(deep==48){
            counts++;
        }
        return;
    }

    // 剪枝：曼哈顿距离判断
    int remaining = 48 - deep;
    int dist = abs(x - 6) + abs(y);
    if(dist > remaining || (remaining - dist) % 2 != 0){
        return;
    }

    // 检查当前位置是否已访问
    if(graph[x][y] == 1){
        return;
    }

    // 标记当前位置为已访问
    graph[x][y] = 1;

    if(dirs[deep] == -1){
        // 通配符，尝试四个方向
        for(int i=0;i<4;i++){
            int xx = x + turn[i].first;
            int yy = y + turn[i].second;
            if(xx >=0 && xx <7 && yy >=0 && yy <7){
                dfs(xx, yy, deep+1, counts, graph, dirs);
            }
        }
    }else {
        // 固定方向
        int xx = x + turn[dirs[deep]].first;
        int yy = y + turn[dirs[deep]].second;
        if(xx >=0 && xx <7 && yy >=0 && yy <7){
            dfs(xx, yy, deep+1, counts, graph, dirs);
        }
    }

    // 回溯，取消标记
    graph[x][y] = 0;
}

int main()
{   
    string s;
    cin >> s;
    int counts = 0;
    int graph[7][7] = {0};
    int dirs[48];
    memset(dirs, -1, sizeof(dirs));

    for(int i=0;i<s.size();i++){
        if(s[i]=='U') dirs[i] = 0;
        else if(s[i]=='R') dirs[i] = 1;
        else if(s[i]=='D') dirs[i] = 2;
        else if(s[i]=='L') dirs[i] = 3;
    }

    dfs(0,0,0, counts, graph, dirs);
    cout << counts << endl;
    return 0;
}

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