類型： 隱式圖搜索
原題：
There are three jugs with a volume of a, b and c liters. (a, b, and c are positive integers not greater than 200). The first and the second jug are initially empty, while the third
is completely filled with water. It is allowed to pour water from one jug into another until either the first one is empty or the second one is full. This operation can be performed zero, one or more times.
You are to write a program that computes the least total amount of water that needs to be poured; so that at least one of the jugs contains exactly d liters of water (d is a positive integer not greater than 200). If it is not possible to measure d liters this way your program should find a smaller amount of water d' < d which is closest to d and for which d' liters could be produced. When d' is found, your program should compute the least total amount of poured water needed to produce d' liters in at least one of the jugs.
Input
The first line of input contains the number of test cases. In the next T lines, T test cases follow. Each test case is given in one line of input containing four space separated integers - a, b, c and d.
Output
The output consists of two integers separated by a single space. The first integer equals the least total amount (the sum of all waters you pour from one jug to another) of poured water. The second integer equals d, if d liters of water could be produced by such transformations, or equals the closest smaller value d' that your program has found.
樣例輸入：
2
2 3 4 2
96 97 199 62
樣例輸出：
2 2
9859 62
題目大意：
有三個杯子它們的容量分別是a,b,c, 並且初始狀態下第一個和第二個是空的， 第三個杯子是滿水的。可以把一個杯子的水倒入另一個杯子，當然，當被倒的杯子滿了或者倒的杯子水完了，就不能繼續倒了。
你的任務是寫一個程序計算出用最少的倒水量，使得其中一個杯子裡有d升水。如果不能倒出d升水的話，那麼找到一個d' < d ，使得d' 最接近d。
分析與總結：
因為共有3個水杯， 根據每一杯的水量v1,v2,v3, 可以得到一個狀態state(v1,v2,v3);
為了方便進行dfs搜索的狀態轉移，可以用兩個三維數組volume[3], state[3]分別表示三個杯子的容量和狀態。然後會有倒水的動作，可以從第1個杯子倒入第2，3個，從第2個倒入第1，3個等等……所以用兩個for循環，可以遍歷出所有的倒水方案。
然後注意一些不能倒水的條件，比如要倒的杯子是空的，目標杯子是滿的，則不進行倒水的動作。
網上解題報告的方法： 用bfs做
[cpp]
// dfs，隱式圖搜索
// Time: 0.072 s (UVA)
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int d, volume[3], state[3], minVolume, d1;
bool flag, vis[205][205][205];
void search(int tot){
// 更新結果的狀態，有不少地方需要注意
for(int i=0; i<3; ++i){
if(state[i] && state[i] == d){
d1 = d;
if(!flag) minVolume = tot; // 第一次發現等於d，那麼直接把當前總量tot賦給minVolume
else if(tot<minVolume) minVolume = tot; // 以後有其他情況等於d的，只有tot小於minVolume才更新
flag=true; // 標志為已經找到等於d的了
}
else if(!flag && state[i] && state[i] < d){// 注意： ！flag表示只有沒有找到等於d的情況，才會執行下面這些語句
if(d-state[i]<d1){
d1 = d-state[i];
minVolume = tot;
}
else if(d-state[i]==d1 && tot<minVolume)
minVolume = tot;
}
}
for(int i=0; i<3; ++i){
for(int j=0; j<3; ++j)if(i!=j && state[i] && state[j]!=volume[j] ){
int add;
int tmp_i = state[i], tmp_j = state[j]; // 備份，回溯後要恢復
if(state[i] >= volume[j]-state[j]){ // 如果倒的水大於等於被倒杯子剩余容量，那麼將被倒滿
add = volume[j]-state[j];
state[i] -= add;
state[j] = volume[j];
}
else{ // 否則，全部倒光到目標杯子裡
state[j] += state[i];
add = state[i];
state[i] = 0;
}
if(!vis[state[0]][state[1]][state[2]]){
vis[state[0]][state[1]][state[2]] = true;
search(tot+add);
vis[state[0]][state[1]][state[2]] = false; // 回溯，恢復狀態
}
state[i] = tmp_i; // 回溯，恢復狀態
state[j] = tmp_j;
}
}
}
int main(){
int T;
scanf("%d", &T);
while(T--){
scanf("%d%d%d%d",&volume[0],&volume[1],&volume[2],&d);
state[0]=0, state[1]=0, state[2]=volume[2];
memset(vis, 0, sizeof(vis));
vis[0][0][volume[2]] = true;
flag = false;
minVolume = d1 = 1000000;
search(0); www.2cto.com
if(flag) printf("%d %d\n", minVolume, d1);
else printf("%d %d\n", minVolume, d-d1);
}
return 0;
}
