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

題目簡介

在 p×q 棋盤（p*q ≤ 26）上，騎士走「日」字（8 種方向）。求能否遍歷所有格子恰好一次，若能輸出字典序最小的路徑（格子名如 A1, B3...），否則輸出 impossible。

解題思路

深度優先搜索 + 回溯：

1. 從 A1 (0,0) 開始，按字典序嘗試 8 個方向（方向數組按目標格子名排序）。
2. 遞歸搜索，標記訪問，路徑存入數組。
3. 若走完所有格子（步數 = p*q），記錄路徑並返回成功。
4. 利用全局標誌位剪枝：找到解後直接返回，不再嘗試其他分支。

代碼實現

#include <cstdio>
#include <cstring>
const int dx[8] = {-2,-2,-1,-1,1,1,2,2};
const int dy[8] = {-1,1,-2,2,-2,2,-1,1};
const char col[26] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
char pathX[28]; int pathY[28];
int vis[28][28], p, q, total, step;
bool found;

void dfs(int x, int y, int cnt) {
    if (cnt == total) { found = true; return; }
    for (int i = 0; i < 8; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx < 0 || nx >= q || ny < 0 || ny >= p || vis[nx][ny]) continue;
        vis[nx][ny] = 1;
        dfs(nx, ny, cnt+1);
        if (found) { pathX[step] = col[x]; pathY[step++] = y+1; return; }
        vis[nx][ny] = 0;
    }
}

int main() {
    int T; scanf("%d", &T);
    for (int cs = 1; cs <= T; cs++) {
        scanf("%d %d", &p, &q);
        total = p * q; step = 0; found = false;
        memset(vis, 0, sizeof(vis));
        vis[0][0] = 1;
        dfs(0, 0, 1);
        printf("Scenario #%d:\n", cs);
        if (!found) puts("impossible");
        else {
            for (int i = step-1; i >= 0; i--) printf("%c%d", pathX[i], pathY[i]);
            puts("");
        }
        if (cs < T) puts("");
    }
    return 0;
}

複雜度分析

棋盤最大 26 格，DFS 狀態空間極小，瞬間出結果。