題目所屬： 隱式圖的搜索
題目意思： 有三個容器大小為 a b c 剛開始 a b都是空的 c是滿的，現在給定一個d 大小的水量 ，要求我麼找到最小的倒水總量使得有一個容器的水量為 d，如果找不到那麼就用d'代替d（d' < d）直到能夠找到有一個容器的水量為 d為止，最後輸出 最小的倒水總量和 d'
解題思路： 倒水條件：假設是a倒入b中，那麼必須要有a被倒空或 b 被倒滿。
經典的倒水問題，只是結果是要我們輸出最小的倒水總量而不是次數，這個需要注意。我們知道對於三個容器而言，裡面就是水裝的多不多，那麼我麼就知道這個容器的狀態就是水的多少，那麼開始的狀態就是（0 ， 0 ， c），我們還知道如果容器a有水那麼它可以選擇倒到b 和 c ，其它類似。那麼這個解空間樹就是一個多叉樹，我們就可以通過BFS進行搜索，搜索每一狀態，那麼我麼只要開一個結構體裡面放三個容器的水量和當前狀態的最小倒水總量，那麼只要找到有一個容器的水量為d，那麼我們就可以去更新ans（判斷ans是否大於當前的minsum）。如果沒辦法倒出d的水量，那麼我麼就用一個循環往下搜索直到找到d'。最後輸出ans 和 d
代碼：
[cpp]
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <cstdio>
#include <stack>
#include <queue>
using namespace std;
#define MAXN 210
int t , ans;
int vis[MAXN][MAXN][MAXN];//標記狀態是否出現過
int jugs[3] , d;
struct Node{//結構體存儲三個容器的水量和當前狀態的最小倒水總量
int v[3];
int minsum;
};
queue<Node>q;
void Bfs(){
while(!q.empty())
q.pop();
memset(vis , 0 , sizeof(vis));
ans = 999999999;//初始化為無窮大
vis[0][0][jugs[2]] = 1; //初始狀態
Node tmp;
tmp.v[0] = 0;
tmp.v[1] = 0;
tmp.v[2] = jugs[2];
tmp.minsum = 0;
q.push(tmp);//第一個狀態先入對列
while(!q.empty()){
Node tmp = q.front();
q.pop();
for(int i = 0 ; i < 3 ; i++){//枚舉三個容器
if(tmp.v[i] == d){//只要有一個容器的水量為d就判斷並且跳出該次的循環
if(ans > tmp.minsum)
ans = tmp.minsum;
break;
}
else{
for(int j = 0 ; j < 3 ; j++){//這個就是去判斷容器v[i]能不能夠倒水到v[j]。
if(i != j){//倒水前提是不同一個容器
Node Tmp = tmp;
if(tmp.v[i] && jugs[j] - tmp.v[j]){//如果v[i]有水並且v[j]有剩余的空間可以存水才滿足
int min = tmp.v[i] < jugs[j] - tmp.v[j] ? tmp.v[i] : jugs[j] - tmp.v[j];//找到兩者中的最小這樣才能滿足倒水的條件
Tmp.minsum += min;//當前倒水量加上min
Tmp.v[i] -= min;//容器相應減少水量
Tmp.v[j] += min;//容器相應減少水量
if(!vis[Tmp.v[0]][Tmp.v[1]][Tmp.v[2]]){//如果這個狀態沒出現過才push進隊列
vis[Tmp.v[0]][Tmp.v[1]][Tmp.v[2]] = 1;
q.push(Tmp);
}
}
}
}
}
}
}
}
int main(){
scanf("%d" , &t);
while(t--){
scanf("%d%d%d%d" , &jugs[0] , &jugs[1] , &jugs[2] , &d);
Bfs();
if(ans == 999999999){////如果需要繼續Bfs
while(1){
d--;//向下搜索
Bfs();
if(ans != 999999999) break;//只要找到滿足就退出
}
}
printf("%d %d\n" , ans , d);//最後輸出結果
} www.2cto.com
return 0;
}
