Description - 問題描述
輸入只有一行，即4個整數：
xMax yMax zMax n
其中100>xMax>yMax>zMax，n<100
Output - 輸出數據
對於每個測試數據，輸出其倒水步驟，如果步驟只有一步，step不加s請參考Sample Output，無解的話輸出“No Solution”
算法分析
首先，我們需要考慮倒出者和接收者的可能分別為x->y,x->z（前提是x>0);y->x,y->z（前提是y>0);z->x,z->y（前提是z>0)共6種可能，接下來我們便對其進行詳細分析。
①x->y時
前提：if（x>0),接著，我們要考慮的就是當將x中所有水倒入y中，是否已經超過了y的容量，代碼如下
1 if(x>0)
2 {
3 if(x+y>ymax)
4 {
5 x=x-(ymax-y);//將x中所有水倒入y中時已超出y的最大容量
6 y=ymax;
7 }
8 else
9 {
10 y=x+y;//將x中所有水倒入y中後未超過其最大容量
11 x=0;//即x中的水全部倒入y中，x變為空
12 }
13 }
②x->z時
前提：if(x>0)這時，我們可以將x->z的過程類比成x->y的過程，其實際上的過程是一樣的，代碼如下：
1 if(x>0)
2 {
3 if(x+z>zmax)
4 {
5 x=x-(zmax-z);//z容器倒滿
6 z=zmax;
7 }
8 else
9 {
10 z=z+x;//x倒空
11 x=0;
12 }
13 }
③y->x時
前提：if(y>0),這是，我們還要不要像以前那樣考慮y會不會倒空，已及x會不會倒滿呢？其答案是否定的，為什麼呢？你可以設想：在整個裝置（包括x，y以及z）中，其總水量之和為xmax。故不管y如何倒都不會使x>xmax，代碼如下：
1 if(y>0)
2 {
3 x=x+y;//y倒空
4 y=0;
5 }
④y->z時,同x->y
⑤z->x時,同y->x
⑥z->y,這裡也是同y->x嗎？其實不然，當y->x時，無論如何都不會使x>xmax。但當z->y時卻有可能使y>ymax，很多人都跳入了這個坑裡，導致最終程序不能ac。經過仔細思考之後，其實可以知道這是和x->y一樣的。代碼如下：
1 if(z>0)
2 {
3 if(z+y>ymax)
4 {
5 z=z-(ymax-y);
6 y=ymax;
7 }
8 else
9 {
10 y=y+z;
11 z=0;
12 }
13 }
在對倒水的過程進行詳細分析之後，最重要的便是算法的構造。仔細分析可以知道，這道題是要求我們分析倒水的每種情況，然後找出最優解。毫無疑問，這便是bfs的思路。可能有些人不了解或對bfs接觸較少，這裡給上百度對其的解釋以助理解：
BFS一般指寬度優先搜索，寬度優先搜索算法（又稱廣度優先搜索）是最簡便的圖的搜索算法之一，這一算法也是很多重要的圖的算法的原型。Dijkstra單源最短路徑算法和Prim最小生成樹算法都采用了和寬度優先搜索類似的思想。其別名又叫BFS，屬於一種盲目搜尋法，目的是系統地展開並檢查圖中的所有節點，以找尋結果。換句話說，它並不考慮結果的可能位置，徹底地搜索整張圖，直到找到結果為止。而在這個問題中，我們使用隊列（queue）來實現之。
首先，假設我們已經定義了一個隊列q，如下所示
struct node
{
int qx,qy,qz;
int pre;
} q[maxn];
其中qx，qy，qz表示當前各個裝置中水的含量，而對於pre，相信大多數人都會納悶：這是用來干什麼的呢？其實，當你仔細閱讀題目便可知道，它不僅要求輸出最少次數，還得打印出每倒一次水的步驟，這裡的pre便是用以存儲當前狀態所對應的上一個狀態，到最後輸出時，只需沿著pre進行輸出即可。
每倒一次水，就想當於產生了一個新的狀態，於是就要判斷這個狀態是否已達到目標。因此每倒一次水，就要調用一次push過程，將新狀態入隊，然後判斷隊尾元素是否已是解，push的代碼如下： 1 void push()
2 {
3 bool can_push=true;
4 for(int i=1;i<=rear;i++)
5 {
6 if(q[i].qx==x&&q[i].qy==y&&q[i].qz==z)
7 {
8 can_push=false;
9 return;
10 }
11 }
12 if(can_push)
13 {
14 rear++;
15 q[rear].qx=x;
16 q[rear].qy=y;
17 q[rear].qz=z;
18 q[rear].pre=front;
19 }
20 }
同時，在倒水時如果先前已經出現了與當前狀態一致的狀態，那還要不要繼續倒呢？顯然，答案是否定的，而這裡的bool型變量can_push正是幫助完成了這一點.
在倒完水後，我們還需判斷是否達到了目標狀態，如果達到了就跳出循環，然後輸出過程，代碼如下：
void is_target()
{
if(q[rear].qx==n||q[rear].qy==n||q[rear].qz==n)
flag=true;
else
flag=false;
}
細心的人可能會發現：在模擬倒水過程時的x，y，z三個變量是哪來的呢？以是，我們還得寫個取隊首元素的函數，代碼如下;
void initial()
{
x=q[front].qx;
y=q[front].qy;
z=q[front].qz;
}
最後，我們再將剛剛模擬過的6種情況寫下，再加一個while循環便可完成任務。接下來還有一點值得思考：這裡的while循環的條件是什麼。還記得題目中給出的“No Solution”嗎。是的，在最後跳出循環後我們還得加一條is_target()(其實在跳出循環之前已經執行了一次is_target()，故只需判斷flag即可)以判斷是否有解。經過這樣的分析後，while執行的條件便是隊列是否為空is_empty()。倒水總過程的代碼如下：
1 void pour()
2 {
3 while(front <= rear)
4 {
5 initial();
6 //x->y
7 if(x>0)
8 {
9 if(x+y>ymax)
10 {
11 x=x-(ymax-y);
12 y=ymax;
13 }
14 else
15 {
16 y=x+y;
17 x=0;
18 }
19 }
20 push();
21 is_target();
22 if(flag)
23 break;
24 //x->z
25 initial();
26 if(x>0)
27 {
28 if(x+z>zmax)
29 {
30 x=x-(zmax-z);
31 z=zmax;
32 }
33 else
34 {
35 z=z+x;
36 x=0;
37 }
38 }
39 push();
40 is_target();
41 if(flag)
42 break;
43 //y->x
44 initial();
45 if(y>0)
46 {
47 x=x+y;
48 y=0;
49 }
50 push();
51 is_target();
52 if(flag)
53 break;
54 //y->z
55 initial();
56 if(y>0)
57 {
58 if(y+z>zmax)
59 {
60 y=y-(zmax-z);
61 z=zmax;
62 }
63 else
64 {
65 z=y+z;
66 y=0;
67 }
68 }
69 push();
70 is_target();
71 if(flag)
72 break;
73 //z->x
74 initial();
75 if(z>0)
76 {
77 x=x+z;
78 z=0;
79 }
80 push();
81 is_target();
82 if(flag)
83 break;
84 //z->y
85 initial();
86 if(z>0)
87 {
88 if(z+y>ymax)
89 {
90 z=z-(ymax-y);
91 y=ymax;
92 }
93 else
94 {
95 y=y+z;
96 z=0;
97 }
98 }
99 push();
100 is_target();
101 if(flag)
102 break;
103 front++;
104 }
105 }
還有一點要補充的就是這題也可以用STL裡的queue來做，這樣便可省去自己寫隊列的麻煩。
最後，給上OJ上ac的代碼，僅供參考：
1 /*
2 Name: lwq
3 Copyright:
4 Author:
5 Date: 07/12/14 00:57
6 Description: 1777
7 */
8
9 #include<iostream>
10 using namespace std;
11 const int maxn=10000+10;
12 int front,rear;
13 int xmax,ymax,zmax;
14 int n;
15 int x,y,z;
16 int step=0;
17 int k=0;
18 bool flag=false;
19 struct node
20 {
21 int qx,qy,qz;
22 int pre;
23 } q[maxn];
24 struct node_data
25 {
26 int x,y,z;
27 }data[maxn];
28 void is_target()
29 {
30 if(q[rear].qx==n||q[rear].qy==n||q[rear].qz==n)
31 flag=true;
32 else
33 flag=false;
34 }
35 void initial()
36 {
37 x=q[front].qx;
38 y=q[front].qy;
39 z=q[front].qz;
40
41 }
42 void push()
43 {
44 bool can_push=true;
45 for(int i=1;i<=rear;i++)
46 {
47 if(q[i].qx==x&&q[i].qy==y&&q[i].qz==z)
48 {
49 can_push=false;
50 return;
51 }
52 }
53 if(can_push)
54 {
55 rear++;
56 q[rear].qx=x;
57 q[rear].qy=y;
58 q[rear].qz=z;
59 q[rear].pre=front;
60 }
61 }
62 void pour()
63 {
64 while(front <= rear)
65 {
66 initial();
67 //x->y
68 if(x>0)
69 {
70 if(x+y>ymax)
71 {
72 x=x-(ymax-y);
73 y=ymax;
74 }
75 else
76 {
77 y=x+y;
78 x=0;
79 }
80 }
81 push();
82 is_target();
83 if(flag)
84 break;
85 //x->z
86 initial();
87 if(x>0)
88 {
89 if(x+z>zmax)
90 {
91 x=x-(zmax-z);
92 z=zmax;
93 }
94 else
95 {
96 z=z+x;
97 x=0;
98 }
99 }
100 push();
101 is_target();
102 if(flag)
103 break;
104 //y->x
105 initial();
106 if(y>0)
107 {
108 x=x+y;
109 y=0;
110 }
111 push();
112 is_target();
113 if(flag)
114 break;
115 //y->z
116 initial();
117 if(y>0)
118 {
119 if(y+z>zmax)
120 {
121 y=y-(zmax-z);
122 z=zmax;
123 }
124 else
125 {
126 z=y+z;
127 y=0;
128 }
129 }
130 push();
131 is_target();
132 if(flag)
133 break;
134 //z->x
135 initial();
136 if(z>0)
137 {
138 x=x+z;
139 z=0;
140 }
141 push();
142 is_target();
143 if(flag)
144 break;
145 //z->y
146 initial();
147 if(z>0)
148 {
149 if(z+y>ymax)
150 {
151 z=z-(ymax-y);
152 y=ymax;
153 }
154 else
155 {
156 y=y+z;
157 z=0;
158 }
159 }
160 push();
161 is_target();
162 if(flag)
163 break;
164 front++;
165 }
166 }
167 int main()
168 {
169 front=1,rear=1;
170 cin>>xmax>>ymax>>zmax;
171 cin>>n;
172 q[front].qx=xmax;
173 q[front].qy=0;
174 q[front].qz=0;
175 pour();
176
177
178 if(flag)
179 {
180
181
182 while(q[rear].pre>0)
183 {
184 k++;
185 data[k].x=q[rear].qx;
186 data[k].y=q[rear].qy;
187 data[k].z=q[rear].qz;
188 rear=q[rear].pre;
189 }
190 if(k>1)
191 cout<<k<<' '<<"steps"<<endl;
192 else
193 cout<<k<<' '<<"step"<<endl;
194 cout<<"step0:"<<' '<<xmax<<' '<<'0'<<' '<<'0'<<endl;
195 for(int i=k;i>=1;i--)
196 {
197 cout<<"step"<<k-i+1<<':'<<' '<<data[i].x<<' '<<data[i].y<<' '<<data[i].z<<endl;
198 }
199 }
200 else
201 {
202 cout<<"No Solution"<<endl;
203 }
204 return 0;
205 }
最後，還要感謝YYL大神的不啬指教以及xaero的ppt。
這是我的第一篇博文，歡迎各位大神的指點。
