UVA 10651 Pebble Game：狀態壓縮 DFS/BFS 解棋盤遊戲

題目大意

12 孔棋盤，初始有棋子佔據某些孔。移動規則：一顆棋子跳過相鄰棋子落入緊鄰空孔，被跳過棋子被移除（類似跳棋）。求可達狀態中棋子最少數量，及對應移動步驟。

狀態壓縮

12 孔 → 12 位整數 state (0~4095)，bit=1 表示有棋子。總狀態數 4096，極小。

DFS + 備忘錄搜索所有可達狀態

從初始狀態出發，遞歸嘗試所有合法移動，記錄訪問過的狀態（vis[state]=true）。搜索結束後，遍歷所有 vis[state]=true，找 popcount(state) 最小者。

移動生成邏輯

預計算所有合法三元組 (from, mid, to)：
水平：(0,1,2), (1,2,3), ...
垂直：(0,4,8), (1,5,9), ...
共 24 種移動模式。
移動合法條件：(state>>from&1) && (state>>mid&1) && !(state>>to&1)。

C++ 代碼（DFS 版）

#include 
using namespace std;
const vector> moves = {
    {0,1,2},{1,2,3},{3,4,5},{4,5,6},{6,7,8},{7,8,9},{9,10,11},{10,11,12}, // 示例，實際需列全
    // ... 此處省略完整 24 組三元組，比賽時建議手寫或代碼生成
};
bool vis[1<<12];
int best = 13, bestState;

void dfs(int state) {
    if (vis[state]) return;
    vis[state] = true;
    int cnt = __builtin_popcount(state);
    if (cnt < best) { best = cnt; bestState = state; }
    for (auto &m : moves) {
        int from=m[0], mid=m[1], to=m[2];
        if ((state>>from&1) && (state>>mid&1) && !(state>>to&1)) {
            int ns = state ^ (1<> T;
    while (T--) {
        string s; int init = 0;
        for (int i = 0; i < 12; ++i) { cin >> s; if (s[0]=='o') init |= 1<

BFS 版（可輸出移動步驟）
用隊列存 {state, path}，path 記錄移動序列。狀態空間極小，BFS 同樣瞬間結束。

總結
UVA 10651 是「狀態空間 ≤ 2¹²」類問題的教科書案例：位掩碼壓縮狀態 + DFS/BFS 全圖搜索 + 合法移動預計算。同套路解決 UVA 10422、八數碼、燈燈滅等狀態空間搜索問題。