Ural 1298 Knight Moves 完整解析

本題要求在 N×N 棋盤上，從 (0,0) 起點出發，騎士按「日」字走法遍歷所有格子且每格僅走一次。這是經典的漢密爾頓路徑問題，需用 DFS 回溯求解。

核心洞察：方向順序決定成敗

作者實測發現：八個移動方向的嘗試順序直接影響能否找到解。這是因為 DFS 會優先深入第一條可行路徑，錯誤的順序會導致進入死胡同而回溯過久甚至超時。正確的方向陣列順序為：

int dir[8][2] = {
    {2, 1}, {1, 2}, {-1, 2}, {-2, 1},
    {-2, -1}, {-1, -2}, {1, -2}, {2, -1}
};

完整 AC 程式碼

#include <iostream>
#include <vector>
#include <cstring>
#include <cstdio>
using namespace std;

int n;
int dir[8][2] = {{2,1},{1,2},{-1,2},{-2,1},{-2,-1},{-1,-2},{1,-2},{2,-1}};
bool vis[10][10];
vector> path;
int found = 0;

bool dfs(int x, int y, int step) {
    if (step == n * n) { found = 1; return true; }
    
    for (int i = 0; i < 8; i++) {
        int nx = x + dir[i][0];
        int ny = y + dir[i][1];
        if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
        if (vis[nx][ny]) continue;
        
        vis[nx][ny] = true;
        path.push_back({nx, ny});
        
        if (dfs(nx, ny, step + 1)) return true;
        
        path.pop_back();
        vis[nx][ny] = false;
    }
    return false;
}

int main() {
    while (cin >> n) {
        memset(vis, 0, sizeof(vis));
        path.clear();
        found = 0;
        
        vis[0][0] = true;
        path.push_back({0, 0});
        dfs(0, 0, 1);
        
        if (!found) {
            puts("IMPOSSIBLE");
        } else {
            for (auto &p : path) {
                printf("%c%d\n", p.first + 'a', p.second + 1);
            }
        }
    }
    return 0;
}

關鍵技巧總結

• 方向順序至關重要：嘗試順序影響搜尋樹結構，正確順序能大幅剪枝
• DFS + 回溯：標記訪問、遞迴探索、失敗時恢復狀態
• 終止條件：步數達到 N×N 即找到解
• 座標輸出格式：列轉字母（a-j），行轉數字（1-N）

作者心得：「補題已經隔了兩天了...最後又敲了一次，發現過了！找之前的代碼發現就是 dir 數組不一樣，真奇葩，就是走有八個方向，順序不一樣會 WA？」