HDU 1372 Knight Moves：棋盤上騎士最短路徑 BFS

題目大意

標準 8×8 國際象棋棋盤，騎士走「日」字（8 個方向）。給定起點、終點（如 e2 e4），求最少步數。多組測試，輸入以 EOF 結束。

解題思路

無權圖最短路徑 → BFS。狀態為座標 (x,y)，起點入隊，逐層擴展至 8 個合法方向，記錄步數。首次到達終點即為最短步數。

DFS 會超時（重複搜索），BFS 保證最優且高效。座標編碼：pos = x*10 + y（1-based），便於隊列存儲與解碼。

參考代碼 (C++)

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

const int dx[8] = {-2,-1,1,2,2,1,-1,-2};
const int dy[8] = {1,2,2,1,-1,-2,-2,-1};

int bfs(int sx, int sy, int tx, int ty) {
    if (sx == tx && sy == ty) return 0;
    queue<pair<int,int>> q;
    int dist[9][9];
    memset(dist, -1, sizeof(dist));
    q.emplace(sx, sy);
    dist[sx][sy] = 0;
    while (!q.empty()) {
        auto [x, y] = q.front(); q.pop();
        for (int d = 0; d < 8; ++d) {
            int nx = x + dx[d], ny = y + dy[d];
            if (nx < 1 || nx > 8 || ny < 1 || ny > 8) continue;
            if (dist[nx][ny] != -1) continue;
            dist[nx][ny] = dist[x][y] + 1;
            if (nx == tx && ny == ty) return dist[nx][ny];
            q.emplace(nx, ny);
        }
    }
    return -1; // 不可能
}

int main() {
    char s1[4], s2[4];
    while (cin >> s1 >> s2) {
        int sx = s1[0] - 'a' + 1, sy = s1[1] - '0';
        int tx = s2[0] - 'a' + 1, ty = s2[1] - '0';
        int ans = bfs(sx, sy, tx, ty);
        printf("To get from %s to %s takes %d knight moves.\n", s1, s2, ans);
    }
    return 0;
}

關鍵點總結

• BFS 適用於無權圖最短路徑，首次到達即最優。
• 棋盤小（8×8），訪問數組 9×9 足夠。
• 輸入格式為字母+數字，轉換為 1~8 座標。