問題描述:給定 l × l 棋盤(4 ≤ l ≤ 300),騎士從起點 (sx, sy) 移動到終點 (ex, ey),求最小步數。騎士移動方式為「日」字形(8 個方向)。多測試用例。
int vis1[330][330]; // 起點端訪問標記+步數,-1 表示未訪問
int vis2[330][330]; // 終點端訪問標記+步數
int fx[8] = {2,2,-2,-2,1,1,-1,-1};
int fy[8] = {1,-1,1,-1,2,-2,2,-2};
struct Node { int x, y; };
queue<Node> q, w; // 兩端隊列
void biBFS() {
memset(vis1, -1, sizeof(vis1));
memset(vis2, -1, sizeof(vis2));
q.push({sx, sy}); vis1[sx][sy] = 0;
w.push({ex, ey}); vis2[ex][ey] = 0;
while (!q.empty() && !w.empty()) {
// 先擴展起點端一層
int qs = q.size();
while (qs--) {
Node cur = q.front(); q.pop();
// 相遇檢查:當前節點已被終點端訪問
if (vis2[cur.x][cur.y] != -1) {
printf("%d\n", vis1[cur.x][cur.y] + vis2[cur.x][cur.y]);
return;
}
// 擴展 8 方向
for (int i = 0; i < 8; ++i) {
Node nxt = {cur.x + fx[i], cur.y + fy[i]};
if (inside(nxt.x, nxt.y) && vis1[nxt.x][nxt.y] == -1) {
vis1[nxt.x][nxt.y] = vis1[cur.x][cur.y] + 1;
// 關鍵優化:檢查下一層是否已被終點端訪問(奇數步相遇)
if (vis2[nxt.x][nxt.y] != -1) {
printf("%d\n", vis1[nxt.x][nxt.y] + vis2[nxt.x][nxt.y]);
return;
}
q.push(nxt);
}
}
}
// 再擴展終點端一層(對稱邏輯)
int ws = w.size();
while (ws--) { /* 同理,檢查 vis1 */ }
}
}
0 ≤ x,y < l。vis1[sx][sy]=0, vis2[ex][ey]=0,若同點則首次檢查即返回 0。Input:
3
8
0 0
7 0
100
0 0
30 50
10
1 1
1 1
Output:
5
28
0
memset 初始化 -1 必須用 sizeof 而非固定大小。n 後逐個處理。scanf/printf 或關閉同步 ios::sync_with_stdio(false) 加速 IO。雙向 BFS 是解決大狀態空間最短路徑的經典技巧,掌握其「交替擴展 + 相遇檢查」模板,可輕鬆應對 POJ 1915 等同類問題。