首页 > 代码库 > yzoi1777倒水问题的详细解法
yzoi1777倒水问题的详细解法
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进行输出即可。
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()以判断是否有解。经过这样的分析后，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->x105 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->z116 initial();117 if(y>0)118 {119 if(y+z>zmax)120 {121 y=y-(zmax-z);122 z=zmax;123 }124 else125 {126 z=y+z;127 y=0;128 }129 }130 push();131 is_target();132 if(flag)133 break;134 //z->x135 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->y146 initial();147 if(z>0)148 {149 if(z+y>ymax)150 {151 z=z-(ymax-y);152 y=ymax;153 }154 else155 {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 else193 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 else201 {202 cout<<"No Solution"<<endl;203 }204 return 0;205 }
最后，还要感谢YYL大神的不啬指教以及xaero的ppt。
这是我的第一篇博文，欢迎各位大神的指点。
yzoi1777倒水问题的详细解法