題目大意

8×8 棋盤上有 4 個相同棋子。允許移動：1) 移至相鄰空格（上下左右）；2) 跳過相鄰一個棋子落在緊鄰空格（跳棋規則）。給定初始和目標佈局，判斷能否在 ≤8 步內到達。輸入兩行各 8 個整數（4 個棋子的行列坐標），輸出 YES/NO。

核心技術：狀態壓縮 + 雙向 BFS

• 每個棋子坐標 1~8，需 3 位表示行、3 位表示列，共 6 位/子
• 4 個棋子共 24 位，可壓縮為 32 位整數（int）
• 雙向 BFS：從起點和終點各擴展 4 步，中間相遇判斷可達性
• 每步最多 4 子 × 4 方向 = 16 種擴展，總狀態數可控

關鍵實現細節

1. 狀態編碼：將 4 個棋子坐標排序後打包進整數，消除排列順序影響
2. 移動生成：對每個棋子嘗試 4 方向平移/跳躍，檢查邊界、碰撞、目標格為空
3. 雙向相遇：正向 BFS 記錄所有 ≤4 步狀態；反向 BFS 擴展時查找是否在正向集合中
4. 去重：哈希表/布爾數組標記訪問狀態（vis[1<<24] 太大，實際用 unordered_set 或排序數組+二分）

代碼要點（C++）

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;

struct Point { int x, y; bool check() { return x>=0 && x<8 && y>=0 && y<8; } };
struct Node { Point a[5]; int t; } st, ed, e;
int dir[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
bool vis[16777216+1]; // 狀態標記（視具體編碼範圍調整）
int us[65536+10];    // 正向 BFS 記錄的狀態
int len;

// 狀態編碼：4 個棋子坐標排序後壓縮為整數
int get_hash(Point p[]) { /* 實現編碼邏輯 */ }

// 二分查找正向狀態集合
bool find_state(int hash) { /* 在有序 us 中二分查找 */ }

void dfs() {
    // 正向 BFS：從起點擴展 4 步
    // 反向 BFS：從終點擴展 4 步，檢查相遇
    // 詳見完整代碼...
}

int main() {
    while (~scanf("%d%d", &st.a[0].x, &st.a[0].y)) {
        // 讀入起點、終點 4 個棋子坐標
        // 坐標轉 0-based，調用 dfs()
    }
    return 0;
}

複雜度分析

• 時間：雙向 BFS 將擴展因子從 16⁸ 降至 2×16⁴ ≈ 130k，極快
• 空間：存儲正向狀態集合，約數萬級