POJ 3414 Pots：BFS 求解倒水問題最短操作序列

題目背景

擁有兩個容積分別為 A、B 的杯子，允許操作：FILL(i) 裝滿、DROP(i) 倒空、POUR(i,j) 從 i 倒到 j（直到 i 空或 j 滿）。求得到恰好 C 升水的最短操作序列，或判定不可能。

解題思路：狀態空間 BFS

狀態定義

用 (ca, cb) 表示兩杯子當前水量，初始狀態 (0,0)。目標狀態：ca == C || cb == C。

狀態轉移（6 種操作）

1. FILL(1)：(A, cb)
2. FILL(2)：(ca, B)
3. DROP(1)：(0, cb)
4. DROP(2)：(ca, 0)
5. POUR(1,2)：若 ca > B - cb 則 (ca - (B-cb), B)，否則 (0, ca+cb)
6. POUR(2,1)：若 cb > A - ca 則 (A, cb - (A-ca))，否則 (ca+cb, 0)

BFS 流程

• 隊列存儲狀態，v[ca][cb] 記錄訪問。
• 用 p[] 記錄父節點，op[] 記錄操作類型，x[] 記錄操作參數，d[] 記錄步數。
• 找到目標後遞歸輸出路徑。

完整代碼

#include <map>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 105;
int a, b, c, t, le, ri, v[N][N];
int x[N*N], p[N*N], op[N*N], d[N*N];
pair<int, int> q[N*N];

void check(int i, int j, int o, int k) {
    if (v[i][j]) return;
    v[i][j] = 1;
    p[ri] = le;
    op[ri] = o;
    x[ri] = k;
    d[ri] = d[le] + 1;
    q[ri++] = make_pair(i, j);
}

int bfs() {
    int ca, cb = le = ri = 0;
    q[ri++] = make_pair(0, 0);
    memset(v, 0, sizeof(v));
    v[0][0] = 1;
    while (le < ri) {
        ca = q[le].first; cb = q[le].second;
        if (ca == c || cb == c) return le;
        check(a, cb, 1, 1);        // FILL(1)
        check(ca, b, 1, 2);        // FILL(2)
        check(0, cb, 2, 1);        // DROP(1)
        check(ca, 0, 2, 2);        // DROP(2)
        if (ca > b - cb) check(ca - b + cb, b, 3, 1); // POUR(1,2)
        else check(0, ca + cb, 3, 1);
        if (cb > a - ca) check(a, cb - a + ca, 3, 2); // POUR(2,1)
        else check(ca + cb, 0, 3, 2);
        ++le;
    }
    return 0;
}

void print(int k) {
    if (p[k] > 0) print(p[k]);
    if (op[k] == 1) printf("FILL(%d)\n", x[k]);
    if (op[k] == 2) printf("DROP(%d)\n", x[k]);
    if (op[k] == 3) printf("POUR(%d,%d)\n", x[k], 3 - x[k]);
}

int main() {
    int ans;
    while (~scanf("%d%d%d", &a, &b, &c)) {
        if (ans = bfs()) printf("%d\n", d[ans]), print(ans);
        else puts("impossible");
    }
    return 0;
}

樣例解析

輸入：3 5 4
輸出：6 步操作序列，展示了 BFS 保證最短路徑的特性。

複雜度分析

• 狀態數：(A+1)×(B+1) ≤ 101×101 ≈ 10^4。
• 時間/空間：O(A×B)，完全可行。