POJ 2488 A Knight's Journey：DFS 求騎士周遊字典序最小路徑

POJ 2488 A Knight's Journey：DFS 回溯求解

題目大意

p×q 棋盤 (1 ≤ p×q ≤ 26)，騎士從任意格出發，走「日」字步法，尋找訪問**所有格恰好一次**的路徑（騎士周遊）。多解時輸出**字典序最小**路徑（格子命名：列字母 A.. + 行號 1..）。無解輸出 impossible。

解法：DFS + 剪枝 + 字典序搜索順序

• 搜尋起點固定為 A1（字典序最小路徑必從最小格開始）。
• 8 向移動按**目標格字典序**排序：(-1,-2), (1,-2), (-2,-1), (2,-1), (-2,1), (2,1), (-1,2), (1,2) 對應 A1 字典序從小到大。
• 遞迴 DFS，標記訪問，路徑長達 p*q 即找到解，直接返回（保證字典序最小）。
• 資料極小 (≤26)，無需 Warnsdorff 启發式剪枝即可 AC。

完整程式碼（C++）

#include <bits/stdc++.h>
using namespace std;

int p, q, tot;
bool vis[27][27];
int path_x[30], path_y[30], len;
bool found;
const int dir[8][2] = {{-1,-2},{1,-2},{-2,-1},{2,-1},{-2,1},{2,1},{-1,2},{1,2}};

void dfs(int x, int y) {
    if (found) return;
    if (len == tot) {
        found = true;
        for (int i=0;i=1 && nx<=p && ny>=1 && ny<=q && !vis[nx][ny]) {
            vis[nx][ny] = true;
            path_x[len] = nx; path_y[len] = ny; len++;
            dfs(nx, ny);
            vis[nx][ny] = false; len--;
        }
    }
}

int main() {
    int T; scanf("%d", &T);
    for (int cas=1; cas<=T; ++cas) {
        scanf("%d%d", &p, &q);
        tot = p*q;
        memset(vis, 0, sizeof(vis));
        found = false; len = 0;
        vis[1][1] = true; path_x[0]=1; path_y[0]=1; len=1;
        printf("Scenario #%d:\n", cas);
        dfs(1, 1);
        if (!found) printf("impossible");
        puts("\n");
    }
    return 0;
}

關鍵點

• 移動方向順序決定字典序，必須預先排序。
• 找到第一個完整路徑即可停止（字典序最小）。
• 輸出格式：Scenario #i: 後接路徑或 impossible，每組間空行。