HLJOJ 1021 倒水問題：BFS 狀態空間搜索經典實戰

問題描述

有大、中、小三個杯子，容量分別為 a、b、c (1≤a≤b≤c<100)。初始大杯滿水，其餘空。每次操作可將一杯水倒入另一杯，直到源杯空或目標杯滿。判斷能否使某杯恰好有 x 升水 (0

狀態空間建模

• 狀態：三元組 (水量A, 水量B, 水量C)，滿足守恆
• 操作：6 種倒水方向 (A→B, A→C, B→A, B→C, C→A, C→B)
• 目標：任一杯水量等於 x
• 狀態數上限：(a+1)(b+1) ≤ 101×101 ≈ 10^4，極小

標準 BFS 即可求最短步數。

BFS 核心邏輯

int BFS() {
    memset(vis, 0, sizeof(vis));
    queue<Node> q;
    q.push(Node(a, 0, 0, 0)); // 初始狀態
    vis[a][0] = 1;
    while (!q.empty()) {
        Node cur = q.front(); q.pop();
        if (cur.cap[0]==x || cur.cap[1]==x || cur.cap[2]==x) return cur.step;
        for (int i=0; i<3; i++) for (int j=0; j<3; j++) if (i!=j) {
            Node nxt = cur;
            int space = cap[j] - nxt.cap[j]; // 目標杯剩餘容量
            if (nxt.cap[i] && space) {
                if (nxt.cap[i] > space) { nxt.cap[j] = cap[j]; nxt.cap[i] -= space; }
                else { nxt.cap[j] += nxt.cap[i]; nxt.cap[i] = 0; }
                if (!vis[nxt.cap[0]][nxt.cap[1]]) {
                    vis[nxt.cap[0]][nxt.cap[1]] = 1;
                    q.push(Node(nxt.cap[0], nxt.cap[1], nxt.cap[2], nxt.step+1));
                }
            }
        }
    }
    return -1;
}

樣例演示

輸入: 6 3 1 4
輸出: 3
過程: (6,0,0) → (3,3,0) → (3,2,1) → (4,2,0)  ✓ 第3步大杯得4升

輸入: 10 8 7 5
輸出: Impossible

關鍵點總結

• 狀態用二維數組 vis[101][101] 去重（第三杯水量由守恆推導）
• 倒水邏輯分「源杯水量 > 目標剩餘容量」與否兩種情況
• BFS 保證找到最短路徑
• 多組測試數據循環讀取直到 EOF