HDOJ 3309 Roll The Cube：雙球同步滾動 BFS 求最少按鍵次數

題目大意

n×m (≤ 22) 地圖：'.' 空地、'*' 牆、'B' 球 (2個)、'H' 洞 (2個)。上下左右鍵控制**兩球同時向同一方向滾動**，直到撞牆或落入洞。球落入洞後消失（洞也消失）。球不可重疊。求最少按鍵次數使兩球都落入洞。不可達輸出提示語。

狀態定義

狀態 = `(x1, y1, x2, y2, b1, b2, h1, h2)`？實際可簡化：
- 球 1 位置、球 2 位置。
- 球是否已入洞 (`b1`, `b2`)。
- 洞是否已被佔用 (`h1`, `h2`)。
但因球入洞後消失，且洞固定，可用 4 維訪問標記 `vis[x1][y1][x2][y2]`，狀態包含兩球位置（已入洞的球可標記為特殊座標或單獨標記）。

BFS 轉移

• 從當前狀態，嘗試 4 個方向。
• 對每顆球：
  - 若已入洞，位置不變。
  - 否則計算滾動終點：沿方向前進直到下一格為牆或邊界，停在最後一個合法格。
  - 若滾動經過洞，則球入洞（標記入洞，位置可設為洞座標）。
• 檢查兩球新位置是否重疊（且均未入洞）。
• 若狀態未訪問，入隊，步數 +1。
• 若兩球均入洞，返回步數。

關鍵代碼結構

struct State {
    int x[2], y[2];
    bool inHole[2];
    int step;
};

bool vis[22][22][22][22]; // 兩球位置訪問

int bfs() {
    queue q;
    State start = { {sx1, sx2}, {sy1, sy2}, {false, false}, 0 };
    vis[sx1][sy1][sx2][sy2] = true;
    q.push(start);
    while (!q.empty()) {
        State cur = q.front(); q.pop();
        if (cur.inHole[0] && cur.inHole[1]) return cur.step;
        for (int dir = 0; dir < 4; ++dir) {
            State nxt = cur;
            // 滾動邏輯...
            // 檢查重疊、入洞、訪問
            if (!vis[nxt.x[0]][nxt.y[0]][nxt.x[1]][nxt.y[1]]) {
                vis[...] = true;
                nxt.step = cur.step + 1;
                q.push(nxt);
            }
        }
    }
    return -1;
}

複雜度

• 狀態數 ≤ (22×22)² ≈ 23萬，每狀態 4 方向，BFS 可行。

總結

HDOJ 3309 是「多物體同步移動 + 滾動物理 + 狀態空間搜索」的綜合題。關鍵在於正確建模滾動終止條件、入洞消失邏輯、球不可重疊約束，並用 4 維訪問數組去重。BFS 保證最少步數。