此文章目前处于测试阶段，谨慎阅读

题目重述

在一个 7\(\times\)7 的网格中，从左上角(1,1)出发，走到左下角(7,1)，一共走 48 步，恰好经过所有 49 个格子一次（哈密顿路径）。

输入一个长度为 48 的字符串，由 D, U, L, R, ? 组成， ? 表示任意方向。要求统计与模式匹配的路径数量。

已知所有合法路径总数为 88418。

字符串DRURRRRRDDDLUULDDDLDRRURDDLLLLLURULURRUULDLLDDDD的走法如上图所示。

样例输入输出

??????R??????U??????????????????????????LD????D?

201

核心思路：DFS + 强剪枝

最直观的解法是深度优先搜索（DFS），枚举所有可能的路径。

状态定义：

1. 当前坐标 (x, y)
2. 已走步数 step （从 0 开始，到 48 步结束）
3. vis[10][10] 数组标记已访问的格子

搜索过程：
每一步根据模式字符 \( str[step] \) 决定可尝试的方向：

• 若为 ? 则尝试四个方向（右、左、下、上）
• 否则仅尝试指定方向

但暴力的 DFS 复杂度高达 \( O(4^{48}) \)，绝对会超时。因此，剪枝才是这道题真正的灵魂。

剪枝条件详解

代码在递归调用前，检查了四种几何条件。这些条件都是哈密顿路径存在的必要条件（如果不满足，一定无法完成路径，可以安全剪枝）。

1. 区域分割剪枝

// 上下已访问，左右未访问
if(isVis[2] && isVis[3] && !isVis[0] && !isVis[1]) return 0;
// 上下未访问，左右已访问
if(!isVis[2] && !isVis[3] && isVis[0] && isVis[1]) return 0;

其中 isVis[0]=右，isVis[1]=左，isVis[2]=下，isVis[3]=上。

原理： 如果上下都已访问，而左右都未访问，那么未访问区域被已访问的格子分割成了左右两个互不相连的部分。由于路径必须连续，且最终要遍历所有格子，你不可能在左右两块之间跳跃。因此，这条路一定是死路。

对称地，如果左右已访问而上下未访问，同理剪枝。

2. 对角线死胡同剪枝

检查四个对角线方向：

// 左上角
tx=x-1, ty=y-1;
if(tx>=1 && tx<=7 && ty>=1 && ty<=7 && vis[tx][ty] && !isVis[1] && !isVis[3]) return 0;
// 其他三个对角线（左下、右上、右下）类似

原理： 以左上角为例，如果左上角格子已访问，而当前位置的左和上两个邻居都未访问，那么这两个未访问格子之间唯一的连接通道就是左上角格子。但该格子已经走过，无法再进入，所以它们无法连通，路径必然断裂。

其他三个对角线（左下、右上、右下）同理，分别检查对应的两个邻居。

为什么这份代码能通过？

方向顺序优化： 代码使用方向顺序 R, L, D, U（即先右、左、下、上）。虽然终点在左下角，但这样的顺序并不差，且与剪枝条件配合良好。

剪枝强度足够： 上述四个剪枝条件（区域分割 + 对角线死胡同）已经能剔除绝大多数无效分支。对于 \( 7 \times 7 \) 的网格，搜索空间从 \( 4^{48} \) 缩减到数十万级别。

总路径数已知： 所有合法路径只有 88418 条，说明剪枝后需要探索的分支非常有限。即使 ? 较多，实际递归调用次数也在百万级，C++ 能在 0.1 秒内完成。

复杂度分析

理论最坏复杂度： 仍为指数级，但经过剪枝后，实际节点数约为 \( O(10^6) \)。

运行时间： 每次递归常数操作，总运行时间 \( < 0.1 \) 秒。

空间复杂度： vis 数组为 \( O(1) \)，递归深度为 48，空间开销极小。

完整代码实现

#include <iostream>
#include <string>
using namespace std;

string str;
bool vis[10][10];
int ans = 0;

// 方向顺序：右、左、下、上
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

void dfs(int x, int y, int step) {
    // 到达终点且步数正好 48
    if (x == 7 && y == 1) {
        if (step == 48) ans++;
        return;
    }
    
    // 剪枝 1：区域分割
    bool isVis[4];
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        isVis[i] = (nx < 1 || nx > 7 || ny < 1 || ny > 7 || vis[nx][ny]);
    }
    if (isVis[2] && isVis[3] && !isVis[0] && !isVis[1]) return;
    if (!isVis[2] && !isVis[3] && isVis[0] && isVis[1]) return;
    
    // 剪枝 2：对角线死胡同
    // 左上角
    if (x-1 >= 1 && y-1 >= 1 && vis[x-1][y-1] && !isVis[1] && !isVis[3]) return;
    // 左下角
    if (x+1 <= 7 && y-1 >= 1 && vis[x+1][y-1] && !isVis[1] && !isVis[2]) return;
    // 右上角
    if (x-1 >= 1 && y+1 <= 7 && vis[x-1][y+1] && !isVis[0] && !isVis[3]) return;
    // 右下角
    if (x+1 <= 7 && y+1 <= 7 && vis[x+1][y+1] && !isVis[0] && !isVis[2]) return;
    
    vis[x][y] = true;
    
    // 根据模式选择方向
    if (str[step] == '?') {
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx >= 1 && nx <= 7 && ny >= 1 && ny <= 7 && !vis[nx][ny]) {
                dfs(nx, ny, step + 1);
            }
        }
    } else {
        int dir = -1;
        if (str[step] == 'R') dir = 0;
        else if (str[step] == 'L') dir = 1;
        else if (str[step] == 'D') dir = 2;
        else if (str[step] == 'U') dir = 3;
        
        int nx = x + dx[dir], ny = y + dy[dir];
        if (nx >= 1 && nx <= 7 && ny >= 1 && ny <= 7 && !vis[nx][ny]) {
            dfs(nx, ny, step + 1);
        }
    }
    
    vis[x][y] = false;
}

int main() {
    cin >> str;
    dfs(1, 1, 0);
    cout << ans << endl;
    return 0;
}

总结

这份代码通过巧妙利用网格的几何性质进行剪枝，在不使用全局连通性检查的情况下，依然能高效地解决 \( 7 \times 7 \) 哈密顿路径计数问题。

它展示了 DFS + 强剪枝 在中等规模搜索问题中的强大能力，也是 CSES 原题的经典解法之一。写算法题时，剪枝策略往往比算法本身更考验对问题本质的理解。