ZOJ 1005 Jugs 經典水壺問題：模擬與 BFS 兩種解法解析

《虎膽龍威 3》同款經典水壺謎題：給定容量互質的兩壺 A、B 及目標量 N，僅允許「裝滿、倒空、互倒」操作，求使 B 壺恰好盛 N 加侖的操作序列。本文提供貪心模擬法（利用互質特性）與BFS 最短路法兩種解法，並給出 AC 代碼。

問題建模

• 狀態：(a, b) 表示 A、B 當前水量。
• 操作（6 種）：fill A/B、empty A/B、pour A B / B A。
• 目標：b == N（或 a == N，題目要求 B 壺達標）。
• 條件：0 < Ca <= Cb，N <= Cb <= 1000，gcd(Ca, Cb) = 1（互質）。

解法一：貪心模擬（利用互質性質，O(Cb) 步驟）

核心洞察：因互質，反覆「A 裝滿 → 倒入 B → B 滿則倒空」循環，能遍歷 B 壺所有可能水量 (0~Cb-1)，必經 N。

while (1) {
    if (a == 0) { puts("fill A"); a = ca; }          // A 空則裝滿
    if (a == x || b == x) break;                     // 達標退出
    puts("pour A B");                                // A→B
    if (b + a >= cb) { a = b + a - cb; b = cb; }     // B 滿
    else { b += a; a = 0; }
    if (a == x || b == x) break;
    if (b == cb) { puts("empty B"); b = 0; }         // B 滿則倒空
}
puts("success");

樣例 3 5 4 輸出與題目完全一致。代碼極簡，但不保證步驟最少。

解法二：BFS 求最短操作序列（通用、最優）

狀態空間 ≤ 1000×1000 = 1e6，BFS 完全可行。每個狀態存儲前驅狀態與操作，終止時回溯路徑。

struct State { int a, b; };
struct Node { State s; int prev; char op[16]; };

bool bfs(int ca, int cb, int target) {
    queue q;
    vector vis( (ca+1)*(cb+1) ); // 或用 map/unordered_map
    // 初始狀態 (0,0)
    // 6 條邊擴展，判重，記錄前驅與操作
    // 遇到 b==target 回溯輸出
}

BFS 適用於不互質、求最少步驟、操作受限等通用場景。

完整 AC 代碼（貪心模擬版）

#include 
#include 
using namespace std;

int main() {
    int ca, cb, x;
    while (cin >> ca >> cb >> x) {
        int a = 0, b = 0;
        while (1) {
            if (a == 0) { puts("fill A"); a = ca; }
            if (a == x || b == x) break;
            puts("pour A B");
            if (b + a >= cb) { a = b + a - cb; b = cb; }
            else { b += a; a = 0; }
            if (a == x || b == x) break;
            if (b == cb) { puts("empty B"); b = 0; }
        }
        puts("success");
    }
    return 0;
}

測試樣例

Input:
3 5 4
5 7 3

Output:
fill A
pour A B
empty B
pour A B
fill A
pour A B
success
fill B
pour B A
empty A
pour B A
fill B
pour B A
success

總結與擴展

• 互質時貪心模擬最簡潔，利用數論性質（貝祖等式）保證可達性。
• BFS 是通用最優解法，狀態空間小時首選。
• 擴展：三壺問題、帶成本操作、不可逆操作等均可用 BFS/Dijkstra/A* 求解。