POJ 2488 騎士周遊：字典序最小的漢密爾頓路徑完整解析

問題描述

在 p×q 棋盤（1 ≤ p×q ≤ 26）上，騎士（馬）走「日」字步（2 格直 + 1 格橫）。找出一條路徑，使騎士恰好走遍每個格子一次（漢密爾頓路徑）。可從任意格子起始，輸出字典序最小的路徑。無解輸出 "impossible"。

關鍵約束與觀察

• 棋盤最大 26 格（如 2×13, 1×26 等），狀態空間極小
• 騎士移動 8 向：(±2, ±1), (±1, ±2)
• 需字典序最小：優先嘗試字母較小的列（A→Z），再優先數字較小的行（1→p）
• p 對應行號（1~p），q 對應列字母（A~）

解題策略：DFS 回溯 + 剪枝

1. 對每個可能起點（按字典序：A1, A2... B1, B2...）嘗試 DFS
2. 第一個找到的完整路徑即為字典序最小（因起點已按序嘗試）
3. 路徑比較：逐格比較字母優先，再比數字

核心資料結構

int status[100][100];        // 訪問標記
int vex[8] = {-2,-2,2,2,-1,-1,1,1};  // 8 向行位移
int vey[8] = {-1,1,-1,1,-2,2,-2,2};  // 8 向列位移
char path1[1000];            // 最佳路徑列字母
int path2[1000];             // 最佳路徑行號
char prepath1[1000];         // 當前探索路徑
int prepath2[1000];
int top, n, m, key, k, s;    // 全域狀態變數

DFS 遞迴邏輯

void dfs(int x, int y) {
    for (int i = 0; i <= 7; i++) {           // 嘗試 8 個方向
        int xend = x + vex[i];
        int yend = y + vey[i];
        if (合法且未訪問) {
            標記訪問;
            記錄路徑;
            s++;                               // 步數計數
            if (s == n*m) {                    // 走完所有格
                更新最佳路徑（字典序比較）;
            } else {
                dfs(xend, yend);               // 遞迴深入
            }
            回溯：撤銷標記、路徑、步數;
        }
    }
}

字典序比較邏輯

// 比較 prepath (新路徑) 與 path (當前最佳)
int change = -1;
for (int j = 0; j <= n*m-1; j++) {
    if (path1[j] > prepath1[j]) { change = 1; break; }  // 新路徑字母較小
    else if (path1[j] < prepath1[j]) { change = 0; break; }
    else {  // 字母相同，比數字
        if (path2[j] > prepath2[j]) { change = 1; break; }
        else if (path2[j] < prepath2[j]) { change = 0; break; }
    }
}
if (change == 1) 複製 prepath 到 path;

特殊情況處理

• 1×1 棋盤：直接輸出 "A1"
• 無解棋盤：如 2×3、3×3 等，DFS 窮盡後 key=0，輸出 "impossible"
• 起點遍歷順序：雙重迴圈 i=1..n (行), j=1..m (列) → 對應 A1, A2... B1, B2... 確保字典序

完整程式碼架構

int main() {
    scanf("%d", &t);
    for (tem=1; t--; tem++) {
        scanf("%d %d", &n, &m);
        if (n==1 && m==1) { 輸出 A1; continue; }
        
        key = 0;  // 是否找到解
        for (i=1; i<=n; i++) {
            for (j=1; j<=m; j++) {
                初始化狀態;
                從 (i,j) 起始 DFS;
                if (找到解) break;
            }
            if (找到解) break;
        }
        輸出結果;
    }
}

範例驗證

輸入：
3
1 1
2 3
4 3

輸出：
Scenario #1:
A1

Scenario #2:
impossible

Scenario #3:
A1B3C1A2B4C2A3B1C3A4B2C4

複雜度分析

• 狀態數上限：26! 理論極大，但騎士移動極度受限，實際搜尋樹極小
• 最大 26 格，8 向分支，深度 26 → 實際節點數極少（毫秒級）
• 記憶體：O(p×q) 訪問陣列 + O(p×q) 路徑儲存

優化方向（本題不必要但值得知道）

• Warnsdorff 規則：優先走「下一步可選移動最少」的格子，大幅減少回溯
• 位元遮罩：用 32-bit int 表示訪問狀態，加速複製/比較
• 對稱性剪枝：棋盤對稱起點只需試一半

常見坑點

1. 座標系混淆：題目 p=行(數字), q=列(字母)，內部用 x=行, y=列
2. 字典序比較：必須先比字母（列），再比數字（行）
3. 輸出格式：每個 Scenario 後有空行，路徑單行輸出無空格
4. 遞迴深度：最大 26，棧溢位風險極低

這道題是 DFS 回溯求漢密爾頓路徑的經典範例，小規模棋盤讓暴力搜尋成為可行且最簡單的方案，關鍵在於正確處理字典序與輸出格式。