三杯水問題：BFS 求解最少倒水次數

經典水杯倒水問題

給定三個容量不同的水杯，初始時只有最大的水杯裝滿水，其餘兩杯為空。水杯無刻度標記，只能根據已知容量計算水量。任務是編寫程序，找出從初始狀態到達目標狀態所需的最少倒水次數。

問題描述

輸入包含多組測試數據。每組給出三個水杯的體積 V1、V2、V3（滿足 V1 > V2 > V3，V1 < 100，V3 > 0），以及目標狀態 E1、E2、E3（各不超過對應水杯容量）。輸出最少倒水次數，若無法達到目標則輸出 -1。

解題思路：廣度優先搜索 (BFS)

將每個狀態視為圖中的一個節點，狀態由三杯當前水量 (x, y, z) 表示。從初始狀態出發，通過六種可能的倒水操作（任意兩杯之間互倒）生成新狀態，使用 BFS 尋找最短路徑。

• 狀態表示：三維數組 vis[x][y][z] 記錄訪問狀態，f[x][y][z] 記錄前驅節點以重構路徑。
• 倒水規則：從杯 A 倒入杯 B 時，若 A 水量加 B 水量 ≤ B 容量，則 A 空、B 滿；否則 A 剩餘水量減少，B 裝滿。
• 終止條件：隊列為空或找到目標狀態。

核心代碼片段 (C++)

struct Node { int x, y, z; };
queue<Node> q;
bool vis[101][101][101];
Node pre[101][101][101];

void tryPush(const Node& u, Node v) {
    if (!vis[v.x][v.y][v.z]) {
        vis[v.x][v.y][v.z] = true;
        pre[v.x][v.y][v.z] = u;
        q.push(v);
    }
}

// 六種倒水操作
// 1: 0->1, 2: 0->2, 3: 1->0, 4: 1->2, 5: 2->0, 6: 2->1
// 循環調用 tryPush 直到找到目標或隊列為空

複雜度分析

狀態空間上限為 100×100×100 = 10⁶，BFS 時間與空間複雜度均為 O(V1·V2·V3)，在題目限制下完全可行。

範例解析

輸入：6 3 1 4 1 1 (容量 6,3,1；目標 4,1,1)

最短路徑：(6,0,0) → (3,3,0) → (4,2,0) → (4,1,1)，共 3 步。