HDU 1495 非常可樂：BFS 狀態空間搜索（三杯倒水）

問題描述

有三個容器：可樂瓶（容量 S，初始滿）、杯子 N（容量 N）、杯子 M（容量 M），S = N + M，S < 101。允許任意兩容器之間倒水（倒至源空或目標滿）。求能否將可樂平分（即存在兩容器各 S/2），若能輸出最少倒水次數，否則輸出 "NO"。多組測試，0 0 0 結束。

狀態建模

• 狀態：(s, n, m) 表示三容器當前體積。s+n+m = S 恒成立，實際自由度 2。
• 初始狀態：(S, 0, 0)。
• 目標條件：s==S/2 || n==S/2 || m==S/2 且至少兩個容器達到 S/2（因總和為 S，兩個 S/2 意味第三個為 0）。
• 動作：6 種倒水 (s→n, s→m, n→s, n→m, m→s, m→n)。每種倒水量 = min(源體積, 目標剩餘容量)。

BFS 求最短步數

• 狀態空間：S ≤ 100，(s,n,m) 組合 ≤ 101^3 ≈ 100 萬，實際可達狀態極少（受 s+n+m=S 限制）。
• 用三維數組 vis[s][n][m] 記錄步數（或訪問標記 + 隊列存步數）。
• 標準 BFS，首次到達目標狀態即為最少步數。

代碼實現

#include <bits/stdc++.h>
using namespace std;
const int MAXS = 105;

struct State { int s, n, m; };

bool is_goal(const State& st, int S) {
    int half = S / 2;
    int cnt = 0;
    if (st.s == half) ++cnt;
    if (st.n == half) ++cnt;
    if (st.m == half) ++cnt;
    return cnt >= 2;
}

int bfs(int S, int N, int M) {
    static int vis[MAXS][MAXS][MAXS];
    memset(vis, 0, sizeof(vis));
    queue q;
    q.push({S, 0, 0});
    vis[S][0][0] = 1;
    while (!q.empty()) {
        State cur = q.front(); q.pop();
        if (is_goal(cur, S)) return vis[cur.s][cur.n][cur.m] - 1;
        int vol[3] = {cur.s, cur.n, cur.m};
        int cap[3] = {S, N, M};
        for (int from = 0; from < 3; ++from) {
            for (int to = 0; to < 3; ++to) if (from != to) {
                if (vol[from] == 0 || vol[to] == cap[to]) continue;
                State nxt = cur;
                int pour = min(vol[from], cap[to] - vol[to]);
                (&nxt.s)[from] -= pour;
                (&nxt.s)[to] += pour;
                if (!vis[nxt.s][nxt.n][nxt.m]) {
                    vis[nxt.s][nxt.n][nxt.m] = vis[cur.s][cur.n][cur.m] + 1;
                    q.push(nxt);
                }
            }
        }
    }
    return -1;  // 不可達
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int S, N, M;
    while (cin >> S >> N >> M, S||N||M) {
        if (S % 2 != 0) { cout << "NO\n"; continue; }  // 奇數無法平分
        int ans = bfs(S, N, M);
        if (ans == -1) cout << "NO\n";
        else cout << ans << '\n';
    }
    return 0;
}

複雜度

狀態數 ≤ 101×101×101 ≈ 10⁶，BFS 邊數 ≤ 6×狀態數，時間空間均可接受。

優化提示

• 若 S 為奇數直接輸出 "NO"。
• 用 unordered_set 或壓縮狀態 s*101*101 + n*101 + m 可減少內存。