HDU 1813 Escape from Tetris：BFS 狀態壓縮求通用逃脫指令序列

問題描述

N×N 棋盤（N<9），部分格子壞（不可走）。Lele 被隨機放在任意好格子。求一個最短指令序列（上下左右），使無論起始位置，按序執行（撞壁/壞格忽略指令）均能走到邊界逃脫。

狀態建模

狀態 = 所有好格子的位置集合。初始狀態包含所有好格子。每條指令使所有位置嘗試移動，合併相同位置，去除已逃脫（邊界）位置。目標狀態為空集。狀態數 ≤ 2^(N²) ≤ 2^64，但實際可達狀態極少，可用 BFS 搜索。

BFS 搜索最短指令序列

• 狀態用 64 位整數位圖表示（N≤8，共 64 格）。
• 預計算每個格子四方向移動後的目標格子（或原地）。
• BFS 隊列存 (state, path)，訪問集合防重。
• 擴展四方向，計算新狀態，若為 0 輸出路徑。

優化技巧

利用對稱性、預計算移動映射、位運算加速狀態轉移。N=8 時狀態空間約幾萬，BFS 瞬間完成。

代碼框架

struct Node { uint64_t state; string path; };
int dx[4] = {-1,0,1,0}, dy[4] = {0,1,0,-1};
char dirChar[4] = {'N','E','S','W'};

uint64_t moveState(uint64_t s, int d) {
    uint64_t ns = 0;
    for each bit set in s:
        (x,y) = bitPos;
        nx = x+dx[d], ny = y+dy[d];
        if (inBoard && good[nx][ny]) ns |= 1ULL << (nx*N+ny);
        else ns |= 1ULL << (x*N+y); // 撞牆留原地
    return ns & ~escapeMask; // 去除已逃脫位置
}

// BFS 主循環
queue q; unordered_set vis;
q.push({initState, ""}); vis.insert(initState);
while (!q.empty()) {
    auto cur = q.front(); q.pop();
    if (cur.state == 0) { output cur.path; break; }
    for (int d=0; d<4; ++d) {
        uint64_t ns = moveState(cur.state, d);
        if (!vis.count(ns)) { vis.insert(ns); q.push({ns, cur.path+dirChar[d]}); }
    }
}

總結

將「所有起始位置同時模擬」轉化為集合狀態 BFS，位圖壓縮狀態，求最短同步序列，是經典的多源同步規劃問題。