POJ 3414 Pots：BFS 狀態空間搜索 + 路徑回溯（水壺問題）

問題描述

兩水壺容量 A, B (≤100)。操作：FILL(i)、DROP(i)、POUR(i,j)。求最少操作序列使某壺恰有 C 升水。輸出操作數及序列。

狀態定義與 BFS

• 狀態 (v1, v2)：兩壺當前水量。共 (A+1)×(B+1) ≤ 10201 狀態。
• 6 種操作轉移：
  FILL(1): (A, v2) | FILL(2): (v1, B)
  DROP(1): (0, v2) | DROP(2): (v1, 0)
  POUR(1,2): 倒至壺2滿或壺1空
  POUR(2,1): 倒至壺1滿或壺2空
• BFS 從 (0,0) 起，訪問數組 vis[v1][v2]，隊列存儲 {v1,v2,pre,op,curOp} 用於回溯路徑。

路徑回溯

結構體含 pre（父節點隊列下標）、curOp（本步操作編碼 1~6）。找到目標狀態後，沿 pre 反向收集操作編碼，再逆序輸出對應字符串。

參考代碼框架

struct Node { int v1,v2, pre, op, curOp; } q[11000];
bool vis[101][101];
int ans[11000];

void bfs() {
    int h=0, t=0; q[t++] = {0,0,-1,0,0}; vis[0][0]=1;
    while (h < t) {
        Node u = q[h++];
        if (u.v1==C || u.v2==C) {
            printf("%d\n", u.op);
            for (int i=h-1, c=0; i!=-1; i=q[i].pre) ans[c++] = q[i].curOp;
            for (int i=c-1; i>=0; i--) printOp(ans[i]);
            return;
        }
        // 6 操作嘗試入隊...
        // 例如 POUR(2,1):
        Node v = u; v.op = u.op+1; v.curOp = 6;
        v.v1 = min(A, u.v1+u.v2); v.v2 = u.v1+u.v2 - v.v1;
        if (!vis[v.v1][v.v2]) { vis[v.v1][v.v2]=1; v.pre = h-1; q[t++] = v; }
    }
    puts("impossible");
}

總結

經典水壺問題，狀態空間小，BFS 保證最短步數。關鍵在於正確建模 6 種操作的狀態轉移（特別是 POUR 的邊界情況），並用 pre 指針實現路徑記錄。手寫隊列比 STL queue 更便於回溯（可直接用下標）。Special Judge 允許任意最短解。