http://acm.nyist.net/JudgeOnline/problem.php?pid=21
這是一道廣搜的題目， 也是我做的第二道廣搜題目。
廣搜要記住兩點：
1.擴充的節點
2.擴充規則
建構解答樹， 用隊列實作。
1.三個水杯，是大小不一的，初始狀态，0号杯子滿的，1号2号是空的。
2.0->1, 0->2;
1->0, 1->2;
2->0, 2->1;
共六種情況可能出現。
3.一個不空，另一個不滿就可以執行倒水；
4.倒水時，一個杯子可能會把另一個倒滿；也可能不能倒滿；
5.出現過的狀态要進行标記，此處使用了一個三維數組；
6.一旦有一個狀态符合，末狀态便跳出循環。
注：
1.在列舉中間情況時，一種方法是用if将其一一列舉出來，但是代碼量我竟然寫了200多行；另外，還有其他方法，比如使用循環，90行左右。
2.再去尋找下一個杯子時，用了一個“循環數組”， 特别巧妙！
其實，對比兩個代碼，會發現，在變量和結構體的定義上會有不同，特别注意數組的使用。
（一）代碼超長版
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<queue>
#include<iostream>
using namespace std;
int V1, V2, V3;
int E1, E2, E3;
int N;
typedef struct node
{
int x, y, z;
int step;
}Node;
int flag[110][110][110];
int main(void)
{
scanf("%d", &N);
while(N--)
{
scanf("%d%d%d", &V1, &V2, &V3);
scanf("%d%d%d", &E1, &E2, &E3);
queue<Node>Q;
Node head;
memset(flag, 0, sizeof(flag));
head.x = V1;
head.y = 0;
head.z = 0;
head.step = 0;
flag[head.x][head.y][head.z] = 1;
Q.push(head);
while(Q.empty() != 1 || head.x != E1 && head.y != E2 && head.z != E3)
{
Node temp;
head = Q.front();
Q.pop();
if(head.x == E1 && head.y == E2 && head.z == E3)
{
printf("%d\n", head.step);
break;
}
if(head.x != 0 && head.y != V2)//1,2
{
if(head.x + head.y >= V2)
{
temp.x = head.x - (V2 - head.y);
temp.y = V2;
temp.z = head.z;
if(flag[temp.x][temp.y][temp.z] == 0)
{
temp.step = head.step + 1;
Q.push(temp);
flag[temp.x][temp.y][temp.z] = 1;
}
}
else
{
temp.x = 0;
temp.y = head.x + head.y;
temp.z = head.z;
if(flag[temp.x][temp.y][temp.z] == 0)
{
temp.step = head.step + 1;
Q.push(temp);
flag[temp.x][temp.y][temp.z] = 1;
}
}
}
if(head.x != 0 && head.z != V3)//1,3
{
if(head.x + head.z >= V3)
{
temp.x = head.x - (V3 - head.z);
temp.y = head.y;
temp.z = V3;
if(flag[temp.x][temp.y][temp.z] == 0)
{
temp.step = head.step + 1;
Q.push(temp);
flag[temp.x][temp.y][temp.z] = 1;
}
}
else
{
temp.x = 0;
temp.y = head.y;
temp.z = head.x + head.z;
if(flag[temp.x][temp.y][temp.z] == 0)
{
temp.step = head.step + 1;
Q.push(temp);
flag[temp.x][temp.y][temp.z] = 1;
}
}
}
if(head.y != 0 && head.x != V1)//2,1
{
if(head.y + head.x >= V1)
{
temp.x = V1;
temp.y = head.y - (V1 - head.x);
temp.z = head.z;
if(flag[temp.x][temp.y][temp.z] == 0)
{
temp.step = head.step + 1;
Q.push(temp);
flag[temp.x][temp.y][temp.z] = 1;
}
}
else
{
temp.x = head.x + head.y;
temp.y = 0;
temp.z = head.z;
if(flag[temp.x][temp.y][temp.z] == 0)
{
temp.step = head.step + 1;
Q.push(temp);
flag[temp.x][temp.y][temp.z] = 1;
}
}
}
if(head.y != 0 && head.z != V3)//2, 3
{
if(head.y + head.z >= V3)
{
temp.x = head.x;
temp.y = head.y - (V3 - head.z);
temp.z = V3;
if(flag[temp.x][temp.y][temp.z] == 0)
{
temp.step = head.step + 1;
Q.push(temp);
flag[temp.x][temp.y][temp.z] = 1;
}
}
else
{
temp.x = head.x;
temp.y = 0;
temp.z = head.y + head.z;
if(flag[temp.x][temp.y][temp.z] == 0)
{
temp.step = head.step + 1;
Q.push(temp);
flag[temp.x][temp.y][temp.z] = 1;
}
}
}
if(head.z != 0 && head.x != V1)//3, 1
{
if(head.z + head.x >= V1)
{
temp.x = V1;
temp.y = head.y;
temp.z = head.z - (V1 - head.x);
if(flag[temp.x][temp.y][temp.z] == 0)
{
temp.step = head.step + 1;
Q.push(temp);
flag[temp.x][temp.y][temp.z] = 1;
}
}
else
{
temp.x = head.x + head.z;
temp.y = head.y;
temp.z = 0;
if(flag[temp.x][temp.y][temp.z] == 0)
{
temp.step = head.step + 1;
Q.push(temp);
flag[temp.x][temp.y][temp.z] = 1;
}
}
}
if(head.z != 0 && head.y != V2)//3, 2
{
if(head.z + head.y >= V2)
{
temp.x = head.x;
temp.y = V2;
temp.z = head.z - (V2 - head.y);
if(flag[temp.x][temp.y][temp.z] == 0)
{
temp.step = head.step + 1;
Q.push(temp);
flag[temp.x][temp.y][temp.z] = 1;
}
}
else
{
temp.x = head.x;
temp.y = head.y + head.z;
temp.z = 0;
if(flag[temp.x][temp.y][temp.z] == 0)
{
temp.step = head.step + 1;
Q.push(temp);
flag[temp.x][temp.y][temp.z] = 1;
}
}
}
if(Q.empty())
{
printf("-1\n");
break;
}
if(temp.x == E1 && temp.y == E2 && temp.z == E3)
{
printf("%d\n", temp.step);
break;
}
}//if
}//while
return 0;
}
（二）稍微簡約版
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<queue>
#include<iostream>
using namespace std;
int V[3];//體積;
int E[3];//末狀态;
typedef struct node
{
int state[3];//三個狀态;
int step;
}Node;
int N, flag[110][110][110];//标記;
void bfs();
int main(void)
{
scanf("%d", &N);
while(N--)
{
scanf("%d%d%d", &V[0], &V[1], &V[2]);
scanf("%d%d%d", &E[0], &E[1], &E[2]);
memset(flag, 0, sizeof(flag));
bfs();
}//while
return 0;
}
void bfs()
{
queue<Node>Q;
Node head;
head.state[0] = V[0];
head.state[1] = 0;
head.state[2] = 0;
head.step = 0;
flag[head.state[0]][head.state[1]][head.state[2]] = 1;
Q.push(head);
while(Q.empty() != 1 || head.state[0] != E[0] && head.state[1] != E[1] && head.state[2] != E[2])
{
Node temp;
head = Q.front();
Q.pop();
if(head.state[0] == E[0] && head.state[1] == E[1] && head.state[2] == E[2])
{
printf("%d\n", head.step);
return;
}
int i, j, k, top;
for(i = 0; i < 3; i++)//3個水杯;
{
for(k = 0, j = i + 1; k < 2; k++, j++)//
{
temp = head;
top = j % 3;
if(temp.state[i] != 0 && temp.state[top] != V[top])// 一個不空，一個不滿;
{
if(temp.state[i] + temp.state[top] >= V[top])//一個可以把另一個倒滿;
{
temp.state[i] = temp.state[i] - (V[top] - head.state[top]);//head?temp?
temp.state[top] = V[top];
if(flag[temp.state[0]][temp.state[1]][temp.state[2]] == 0)
{
temp.step++;
Q.push(temp);
flag[temp.state[0]][temp.state[1]][temp.state[2]] = 1;
}
}
else //一個不可以把另一個倒滿;
{
temp.state[i] = 0;
temp.state[top] = temp.state[top] + head.state[i];
if(flag[temp.state[0]][temp.state[1]][temp.state[2]] == 0)
{
temp.step++;
Q.push(temp);
flag[temp.state[0]][temp.state[1]][temp.state[2]] = 1;
}
}
if(Q.empty())
{
printf("-1\n");
return;
}
if(temp.state[0] == E[0] && temp.state[1] == E[1] && temp.state[2] == E[2])
{
printf("%d\n", temp.step);
return;
}
}//if
}//for
}//while
}//while
}
解題思路：
三個水杯，大小不一，初始狀态隻有最大的是滿的。分别編号0， 1， 2.畫一下解答樹，也許不難發現是道廣搜題，我發現，分析問題時畫圖還是挺有用的。
1. 一個杯子可以向另外的兩個杯子倒水， 是以，對于0， 1， 2号3個杯子，就有6中情況；
2. 倒水的時候，有一個規則：倒水的杯子（主）不空， 被倒水的杯子（賓）不滿，就可以倒水；（這是一個判斷條件）
3. 在倒水的時候， 又要分兩種情況：一種是一個杯子（主）可以把另一個杯子（賓）倒滿；一種是不能倒滿。相應的要處理的水杯狀态就不一樣了。
4. 優化代碼，就是将原來使用if一一列舉的地方使用了for循環，減少了代碼量。其中，第一個for循環， i控制周遊0， 1, 2三個水杯，第二個for循環，循環兩次，是尋找目前水杯的下一個， 和 下一個的下一個。使用了一個數組，然後又進行了取餘操作，類似于“循環隊列”，這樣就一直可以取0， 1， 2中的數。
5. 優化代碼要注意一下，隊列為空，找不到目标狀态和達到目标狀态這兩種情況必須在每入隊一個時判斷一次。
6. 對比兩種代碼的最大差别就是在類型的定義上：結構的定義，還有體積和末狀态的定義都使用了數組，對于那些重複操作就可以使用for循環了。
![CF1394C 計算幾何[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)