UVA 10603 Fill - 倒水問題 (BFS 狀態空間搜索)

問題描述

三壺容量 a,b,c (≤200)。初始第三壺滿，前兩壺空。允許倒水操作：從一壺倒入另一壺，直到源空或目標滿。求：使任一壺水量恰好為 d 的最小總倒水量（所有倒水量之和）。若不可達 d，找最接近且小於 d 的可達水量 d' 及其最小倒水量。

狀態空間 BFS

• 狀態：(v0,v1,v2) 三壺當前水量，v0+v1+v2 = c 恒定。
• 起始狀態：(0,0,c)，倒水量 0。
• 轉移：枚舉 6 種倒水方向 (i→j, i≠j)，倒水量 t = min(v[i], cap[j]-v[j])，新狀態 v[i]-=t, v[j]+=t，代價 +t。
• 訪問標記：用二維數組 vis[v1][v2]（v0 由 c-v1-v2 決定）。
• BFS 保證最先到達目標狀態的總倒水量最小（邊權非負，BFS 等價於 Dijkstra）。

不可達 d 時的處理

BFS 結束後，若未達到 d，從 d-1 向下檢查是否有狀態含該水量，取第一個找到的（BFS 層序保證其倒水量最小）。

完整代碼

#include <bits/stdc++.h>
using namespace std;
struct State { int v[3], dist; };
int cap[3], target;
bool vis[205][205];
State q[50000]; // 狀態數上限 ~ 200*200

int bfs() {
    memset(vis, 0, sizeof(vis));
    int head=0, tail=0;
    q[tail++] = {{0,0,cap[2]}, 0};
    vis[0][0] = true;
    while(head < tail) {
        State cur = q[head++];
        if(cur.v[0]==target || cur.v[1]==target || cur.v[2]==target)
            return cur.dist;
        for(int i=0;i<3;i++) for(int j=0;j<3;j++) if(i!=j) {
            int pour = min(cur.v[i], cap[j]-cur.v[j]);
            if(pour==0) continue;
            State nxt = cur;
            nxt.v[i] -= pour; nxt.v[j] += pour; nxt.dist += pour;
            if(!vis[nxt.v[1]][nxt.v[2]]) {
                vis[nxt.v[1]][nxt.v[2]] = true;
                q[tail++] = nxt;
            }
        }
    }
    return -1; // 未達到 target
}

int main() {
    int T; cin>>T;
    while(T--) {
        cin>>cap[0]>>cap[1]>>cap[2]>>target;
        int ans = bfs();
        if(ans != -1) { cout << ans << ' ' << target << endl; continue; }
        // 未達到 target，向下搜索最近可達值
        // 重新 BFS 並記錄所有可達水量的最小倒水量
        memset(vis, 0, sizeof(vis));
        int head=0, tail=0;
        int bestDist[205]; fill(bestDist, bestDist+205, -1);
        q[tail++] = {{0,0,cap[2]}, 0};
        vis[0][0] = true;
        while(head < tail) {
            State cur = q[head++];
            for(int w: cur.v) if(bestDist[w]==-1) bestDist[w]=cur.dist;
            for(int i=0;i<3;i++) for(int j=0;j<3;j++) if(i!=j) {
                int pour = min(cur.v[i], cap[j]-cur.v[j]);
                if(pour==0) continue;
                State nxt = cur;
                nxt.v[i] -= pour; nxt.v[j] += pour; nxt.dist += pour;
                if(!vis[nxt.v[1]][nxt.v[2]]) {
                    vis[nxt.v[1]][nxt.v[2]] = true;
                    q[tail++] = nxt;
                }
            }
        }
        for(int d=target-1; d>=0; d--) if(bestDist[d]!=-1) {
            cout << bestDist[d] << ' ' << d << endl; break;
        }
    }
    return 0;
}

複雜度

狀態數 ≤ (a+1)(b+1) ≤ 201² ≈ 4萬，BFS 邊數 ≤ 狀態數×6，極快。