POJ 1915 Knight Moves：BFS 求棋盤上騎士最少步數

問題：l×l 棋盤 (4 ≤ l ≤ 300)，騎士從 (sx,sy) 走到 (ex,ey)，輸出最少步數。多測試用例。

BFS 模板

• 狀態：(x, y, step)；
• 8 方向偏移：(-1,-2), (-2,-1), (-2,1), (-1,2), (1,-2), (2,-1), (2,1), (1,2)；
• 訪問標記 vis[x][y]，入隊即標記，防重複；
• 起點 = 終點直接輸出 0。

代碼

#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;

int l, sx, sy, ex, ey;
bool vis[305][305];
int dx[8] = {-1,-2,-2,-1,1,2,2,1};
int dy[8] = {-2,-1,1,2,-2,-1,1,2};

struct Node { int x, y, step; };

int bfs() {
    memset(vis, 0, sizeof(vis));
    queue q;
    q.push({sx, sy, 0});
    vis[sx][sy] = true;
    while (!q.empty()) {
        Node cur = q.front(); q.pop();
        if (cur.x == ex && cur.y == ey) return cur.step;
        for (int i = 0; i < 8; i++) {
            int nx = cur.x + dx[i], ny = cur.y + dy[i];
            if (nx < 0 || nx >= l || ny < 0 || ny >= l || vis[nx][ny]) continue;
            vis[nx][ny] = true;
            q.push({nx, ny, cur.step + 1});
        }
    }
    return -1; // 不可達（理論上騎士圖連通）
}

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        scanf("%d%d%d%d%d", &l, &sx, &sy, &ex, &ey);
        printf("%d\n", bfs());
    }
    return 0;
}

複雜度

• 狀態數 ≤ 300×300 = 90,000，邊數 ≤ 8×狀態數；
• BFS 時間 O(V+E)，空間 O(V)，極快。