NYOJ 21 三個水杯 - BFS 狀態空間搜索

問題描述

三杯容量 V1>V2>V3，初始最大杯滿，其余空。操作：任意兩杯倒水（倒滿或倒空）。求最少操作次數達到目標狀態 (E1,E2,E3)，不可達輸出 -1。

BFS 狀態定義

狀態 = (水量1, 水量2, 水量3)。初始 (V1,0,0)。每個狀態嘗試 6 種倒水操作（3選2有序對）。訪問標記避免重複。找到目標返回步數。

代碼實現（C++）

#include 
using namespace std;

struct State { int a[3]; int step; };

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        int V[3], target[3];
        cin >> V[0] >> V[1] >> V[2];
        cin >> target[0] >> target[1] >> target[2];
        queue q;
        bool vis[101][101][101] = {}; // 容量≤100
        State start = {{V[0],0,0}, 0};
        q.push(start);
        vis[V[0]][0][0] = true;
        int ans = -1;
        while (!q.empty()) {
            State cur = q.front(); q.pop();
            if (cur.a[0]==target[0] && cur.a[1]==target[1] && cur.a[2]==target[2]) {
                ans = cur.step; break;
            }
            for (int i=0;i<3;i++) for (int j=0;j<3;j++) if (i!=j) {
                if (cur.a[i]==0 || cur.a[j]==V[j]) continue; // 無法倒
                State nxt = cur;
                int pour = min(nxt.a[i], V[j] - nxt.a[j]);
                nxt.a[i] -= pour; nxt.a[j] += pour;
                nxt.step++;
                if (!vis[nxt.a[0]][nxt.a[1]][nxt.a[2]]) {
                    vis[nxt.a[0]][nxt.a[1]][nxt.a[2]] = true;
                    q.push(nxt);
                }
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

關鍵點

• 狀態空間 ≤ 101^3 ≈ 100萬，BFS 可行。
• 倒水邏輯：倒出量 = min(源水量, 目標剩餘容量)。
• 目標狀態可能有多種順序？題目固定順序對應 V1,V2,V3。