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

題目大意

在 p×q（p*q ≤ 26）棋盤上，騎士從任意格出發，走遍所有格恰好一次（不要求回到起點）。輸出字典序最小的路徑（格子命名：列字母 A~ + 行號 1~）。無解輸出 impossible。

DFS 回溯 + 字典序剪枝

騎士移動 8 方向：(-2,-1), (-1,-2), (1,-2), (2,-1), (2,1), (1,2), (-1,2), (-2,1)。
為得到字典序最小路徑，需按目標格字典序從小到大嘗試移動。字典序比較：先比列字母，再比行號。預先計算 8 個方向對應的目標格字典序並排序，或直接按固定順序（經驗順序：左上、左下、右上、右下...）但需驗證。最穩妥：生成所有合法下一步，按 (col, row) 排序後再遞歸。

代碼實現

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 30;

int p, q, vis[MAXN][MAXN], step;
pair path[MAXN*MAXN];
int dx[8] = {-2,-1,1,2,2,1,-1,-2};
int dy[8] = {-1,-2,-2,-1,1,2,2,1};

bool dfs(int x, int y) {
    if (x < 1 || x > p || y < 1 || y > q) return false;
    if (vis[x][y]) return false;
    vis[x][y] = 1;
    path[step++] = {x, char('A' + y - 1)};
    if (step == p * q) return true;
    // 生成合法下一步並按字典序排序
    vector> nxt;
    for (int k = 0; k < 8; ++k) {
        int nx = x + dx[k], ny = y + dy[k];
        if (nx >= 1 && nx <= p && ny >= 1 && ny <= q && !vis[nx][ny])
            nxt.emplace_back(nx, ny);
    }
    sort(nxt.begin(), nxt.end(), [&](auto &a, auto &b) {
        if (a.second != b.second) return a.second < b.second; // 列字母優先
        return a.first < b.first; // 行號其次
    });
    for (auto [nx, ny] : nxt)
        if (dfs(nx, ny)) return true;
    --step; vis[x][y] = 0;
    return false;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int T; cin >> T;
    for (int cs = 1; cs <= T; ++cs) {
        cin >> p >> q;
        memset(vis, 0, sizeof(vis));
        step = 0;
        cout << "Scenario #" << cs << ":\n";
        if (!dfs(1, 1)) cout << "impossible\n";
        else {
            for (int i = 0; i < step; ++i)
                cout << path[i].second << path[i].first;
            cout << '\n';
        }
        if (cs != T) cout << '\n';
    }
    return 0;
}

複雜度

• 最壞情況指數級，但 p*q ≤ 26 且騎士圖稀疏，DFS 回溯極快。
• 字典序排序確保找到的第一條完整路徑即為最小。

關鍵點

• 起點固定為 (1,1) 即 A1，因字典序最小路徑必從 A1 開始（若從 A1 無解則整體無解）。
• 輸出格式：Scenario #i: 後換行，路徑或 impossible，測資間空行。
• 騎士移動方向陣列順序不影響正確性，關鍵在遞歸前排序下一步。