九度 OJ 1147 水壺問題：BFS 狀態搜索與剪枝優化

問題建模

兩水壺容量 A、B，目標在其中一壺得到恰好 Q 升水。允許 6 種操作：裝滿 A/B、倒空 A/B、A→B 倒水、B→A 倒水。求最短操作序列。

BFS 狀態空間

• 狀態：(a, b) 表示兩壺當前水量
• 狀態數上限：(A+1)×(B+1) ≤ 1001×1001
• 訪問標記：bool visited[1001][1001] 防止重複搜索（關鍵剪枝）

核心邏輯

struct Node {
    int a, b;
    vector ops;  // 記錄操作路徑
};

void pour(int from, int to, int capFrom, int capTo, Node &cur) {
    int canPour = min(cur.from, capTo - cur.to);
    cur.from -= canPour;
    cur.to += canPour;
}

void bfs(int A, int B, int Q) {
    queue<Node> q;
    q.push({0, 0, {}});
    visited[0][0] = true;
    
    while (!q.empty()) {
        Node cur = q.front(); q.pop();
        if (cur.b == Q) { output(cur.ops); return; }
        
        // 6 操作嘗試
        for (int op = 0; op < 6; op++) {
            Node nxt = cur;
            applyOp(nxt, op, A, B);
            if (!visited[nxt.a][nxt.b]) {
                visited[nxt.a][nxt.b] = true;
                nxt.ops.push_back(op);
                q.push(nxt);
            }
        }
    }
}

關鍵優化

visited 矩陣 是核心：避免 "反覆倒空" 等無效循環導致狀態爆炸。每個狀態只入隊一次，保證 BFS 找到最短路徑。