POJ 3414 Pots：BFS 求兩水壺問題最短操作序列

問題描述

有兩個水壺，容積分別為 A、B 升。允許操作：

• FILL(i) —— 將壺 i 裝滿
• DROP(i) —— 將壺 i 倒空
• POUR(i,j) —— 從壺 i 向壺 j 倒水，直到 i 空或 j 滿

求得到恰好 C 升水（在任一壺中）的最短操作序列。A,B,C ≤ 100，C ≤ max(A,B)。

狀態空間與 BFS

狀態定為 (x, y) 表示兩壺當前水量。狀態數最多 (A+1)*(B+1) ≤ 101*101 = 10201，極小，適合 BFS。

從 (0,0) 開始 BFS，每個狀態嘗試 6 種操作生成新狀態，記錄前驅狀態及操作類型，直到某壺水量等於 C。若隊列耗盡仍未達到，輸出 "impossible"。

六種操作的狀態轉移

完整代碼

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

struct Node {
    int x, y, pre, op, dist;
} q[110000];

int vis[105][105];
int A, B, C;
int ansOps[110000];

int bfs() {
    memset(vis, 0, sizeof(vis));
    int head = 0, tail = 0;
    q[tail++] = {0, 0, -1, -1, 0};
    vis[0][0] = 1;
    while (head < tail) {
        Node cur = q[head++];
        if (cur.x == C || cur.y == C) {
            // 重構路徑
            int len = cur.dist, idx = head - 1;
            while (q[idx].pre != -1) {
                ansOps[--len] = q[idx].op;
                idx = q[idx].pre;
            }
            return cur.dist;
        }
        // 6 操作
        int nx, ny, nop;
        // FILL(1)
        if (cur.x != A) {
            nx = A; ny = cur.y; nop = 1;
            if (!vis[nx][ny]) {
                vis[nx][ny] = 1;
                q[tail++] = {nx, ny, head-1, nop, cur.dist+1};
            }
        }
        // FILL(2)
        if (cur.y != B) {
            nx = cur.x; ny = B; nop = 2;
            if (!vis[nx][ny]) {
                vis[nx][ny] = 1;
                q[tail++] = {nx, ny, head-1, nop, cur.dist+1};
            }
        }
        // DROP(1)
        if (cur.x != 0) {
            nx = 0; ny = cur.y; nop = 3;
            if (!vis[nx][ny]) {
                vis[nx][ny] = 1;
                q[tail++] = {nx, ny, head-1, nop, cur.dist+1};
            }
        }
        // DROP(2)
        if (cur.y != 0) {
            nx = cur.x; ny = 0; nop = 4;
            if (!vis[nx][ny]) {
                vis[nx][ny] = 1;
                q[tail++] = {nx, ny, head-1, nop, cur.dist+1};
            }
        }
        // POUR(1,2)
        if (cur.x != 0) {
            if (cur.x + cur.y <= B) nx = 0, ny = cur.x + cur.y;
            else nx = cur.x + cur.y - B, ny = B;
            nop = 5;
            if (!vis[nx][ny]) {
                vis[nx][ny] = 1;
                q[tail++] = {nx, ny, head-1, nop, cur.dist+1};
            }
        }
        // POUR(2,1)
        if (cur.y != 0) {
            if (cur.x + cur.y <= A) nx = cur.x + cur.y, ny = 0;
            else nx = A, ny = cur.x + cur.y - A;
            nop = 6;
            if (!vis[nx][ny]) {
                vis[nx][ny] = 1;
                q[tail++] = {nx, ny, head-1, nop, cur.dist+1};
            }
        }
    }
    return -1;
}

int main() {
    while (scanf("%d%d%d", &A, &B, &C) == 3) {
        int steps = bfs();
        if (steps == -1) {
            puts("impossible");
        } else {
            printf("%d\n", steps);
            const char* ops[] = {"", "FILL(1)", "FILL(2)", "DROP(1)", "DROP(2)", "POUR(1,2)", "POUR(2,1)"};
            for (int i = 0; i < steps; i++)
                puts(ops[ansOps[i]]);
        }
    }
    return 0;
}

關鍵點總結

• 狀態空間小，BFS 保證最短步數。
• 需記錄前驅節點與操作類型以重構路徑。
• 訪問標記 vis[x][y] 防止重複入隊。
• 輸出任意一條最短路徑即可。