UVA 10603 Fill：水壺問題的最小倒水量——狀態空間搜索優化

問題描述

三個容量為A,B,C的水壺，初始狀態(0,0,C)。目標獲得恰好target升水（在任一壺中）。操作：將一壺水倒入另一壺直到源空或目標滿。求到達目標的最小總倒水量。若無法達到，輸出最接近且小於target的可達水量及其最小倒水量。

核心難點：狀態重複訪問與最優性

標準BFS用`vis[a][b]`標記狀態(a,b)已訪問。但本題同一狀態可由不同倒水量到達，需記錄到達該狀態的最小倒水量。若後續路徑以更小倒水量到達同狀態，必須更新並繼續搜索。

解法：類Dijkstra的狀態更新

• 狀態：(a,b,c) 三壺水量，和為常數C
• 實際用二維`vis[a][b]`和`vispour[a][b]`記錄最小倒水量
• 隊列中存儲狀態索引，`pour[idx]`記錄到達該狀態的倒水量
• 嘗試插入新狀態時：
  `if(!vis[a][b] || vispour[a][b] > new_pour)` → 更新並入隊

關鍵代碼邏輯

int try_to_insert(int x, int tpour) {
    state &k = st[x];
    if(vis[k[0]][k[1]] != 1 || vispour[k[0]][k[1]] > tpour) {
        vis[k[0]][k[1]] = 1;
        vispour[k[0]][k[1]] = tpour;
        return 1;
    }
    return 0;
}

// BFS主循環
while(front < rear) {
    // 更新record：記錄每種水量的最小倒水量狀態
    for(i=0; i<3; i++)
        if(record[st[front][i]] == 0 || pour[record[st[front][i]]] > pour[front])
            record[st[front][i]] = front;
    
    // 檢查目標
    for(i=0; i<3; i++)
        if(st[front][i] == target) { ... }
    
    // 生成新狀態：6種倒水操作
    for(i=0; i<3; i++) if(w[i] != 0)
        for(j=0; j<3; j++) if(i!=j && w[j] != a[j]) {
            // 計算倒水量pp，新狀態temp
            tpour = pour[front] + pp;
            if(try_to_insert(rear, tpour)) { pour[rear] = tpour; rear++; }
        }
    front++;
}

結果處理

• 若`record[target] != 0` → 直接輸出`pour[ans]`和target
• 否則從target向下找最近可達水量`i`，輸出`pour[record[i]]`和`i`

為何非標準BFS

標準BFS保證「步數最少」，但本題目標是「倒水量最少」。倒水量非單調遞增（不同操作倒水量不同），故需類Dijkstra機制：允許以更小代價重新到達已訪問狀態。

數據範圍

容量≤200，狀態數≤201×201≈4萬，隊列大小20000足夠。