首页 > 代码库 > [Wikioi 1226]倒水问题
[Wikioi 1226]倒水问题
题目描述 Description
有两个无刻度标志的水壶,分别可装 x 升和 y 升 ( x,y 为整数且均不大于 100 )的水。设另有一水 缸,可用来向水壶灌水或接从水壶中倒出的水, 两水壶间,水也可以相互倾倒。已知 x 升壶为空 壶, y 升壶为空壶。问如何通过倒水或灌水操作, 用最少步数能在x或y升的壶中量出 z ( z ≤ 100 )升的水 来。
输入描述 Input Description
一行,三个数据,分别表示 x,y 和 z;
输出描述 Output Description
一行,输出最小步数 ,如果无法达到目标,则输出"impossible"
样例输入 Sample Input
3 22 1
样例输出 Sample Output
14
数据范围及提示 Data Size & Hint
此题数据太弱了,DFS稍微剪枝下都能过,无语
倒水一共有6种策略:
操作1:装满a桶
操作2:装满b桶
操作3:清空a桶
操作4:清空b桶
操作5:将B桶中的水倒入A桶
操作6:将A桶的水倒入B桶
操作2:装满b桶
操作3:清空a桶
操作4:清空b桶
操作5:将B桶中的水倒入A桶
操作6:将A桶的水倒入B桶
每种策略在判断条件后模拟一遍就OK了,不过要注意判重
不管是DFS还是BFS,强调它的判重只需要数组就够了,没必要像ZFX童鞋那样用STL的set,由于x,y<=100,最多有10000种状态,数组不会爆
1、DFS
这里判重数组不仅要保存该结点是否访问过,而且要记录该结点的步数(即解的好坏),便于为后面循环求得最优解
#include <stdio.h>#define MAXN 200#define INF 10000000int f[MAXN][MAXN],a,b,z; //f[x][y]=达到A桶内水量为x,B桶内水量为y的状态所需步骤数void dfs(int x,int y,int step) //x=A桶内水量,y=B桶内水量,step=当前步骤数{ if(f[x][y]!=0&&step+1>=f[x][y]) return; //当前状态已经有解且现在的解一定比过去的解更差时,退出 f[x][y]=step+1; //更新当前状态所需最少步骤数 dfs(x,0,step+1); //1、清空B桶 dfs(0,y,step+1); //2、清空A桶 dfs(x,b,step+1); //3、装满B桶 dfs(a,y,step+1); //4、装满A桶 //5、将B桶倒入A桶 if(x+y<=a) dfs(x+y,0,step+1);//(i)B桶倒空后A桶不会溢出 else dfs(a,x+y-a,step+1); //(ii)B桶倒空后A桶会溢出,故B桶中有残留 //6、将A桶倒入B桶 if(x+y<=b) dfs(0,x+y,step+1);//(i)A桶倒空后B桶不会溢出 else dfs(x+y-b,b,step+1); //(ii)A桶倒空后B桶会溢出,故A桶中有残留}int main(){ int i,j,ans=INF; scanf("%d%d%d",&a,&b,&z); dfs(0,0,0); for(i=0;i<=a;i++) if(f[i][z]!=0) if(f[i][z]<ans) ans=f[i][z]; //遍历所有B桶中达到水量z的情况,获得最优解 for(i=0;i<=b;i++) if(f[z][i]!=0) if(f[z][i]<ans) ans=f[z][i]; //遍历所有B桶中达到水量z的情况,获得最优解 if(ans==INF) printf("impossible\n"); else printf("%d\n",ans-1); return 0;}
2、BFS
BFS做法稍微复杂些,不过和DFS殊途同归,根据BFS的性质,BFS最终搜索出的结果就是最优解,判重数组只需保存每个结点是否访问过就可以了,另外BFS的判重非常重要,否则BFS将进入死循环(我刚开始的代码就是这样,调了一个多小时,ORZ)
#include <stdio.h>#include <stdlib.h>#include <queue>#define MAXN 110using namespace std;int a,b,z,f[MAXN][MAXN]; //目标是取z L水struct cup{ int x; //x桶(大桶)中的水量 int y; //y桶(小桶)中的水量 int sol; //sol=量出的水量 int step; //step=倒水次数}first,now;queue<cup>Q;void extend(cup in) //扩展结点{ if(f[in.x][in.y]!=0) return; f[in.x][in.y]++; in.step++; cup p=in; //操作1:装满a桶 p.x=a; Q.push(p); //操作2:装满b桶 p=in; p.y=b; Q.push(p); //操作3:清空a桶 p=in; p.x=0; Q.push(p); //操作4:清空b桶 p=in; p.y=0; Q.push(p); //操作5:将B桶中的水倒入A桶 p=in; if(in.x+in.y<=a) //(i)B桶倒空后A桶不会溢出 { p.x=in.x+in.y; p.y=0; Q.push(p); } else //(ii)B桶倒空后A桶会溢出,故B桶中有残留 { p.x=a; p.y=in.x+in.y-a; Q.push(p); } //操作6:将A桶的水倒入B桶 p=in; if(in.x+in.y<=b) //(i)A桶倒空后B桶不会溢出 { p.y=in.x+in.y; p.x=0; Q.push(p); } else //(ii)A桶倒空后B桶会溢出,故A桶中有残留 { p.y=b; p.x=in.x+in.y-b; Q.push(p); }}void bfs(){ Q.push(first); while(!Q.empty()) { now=Q.front(); Q.pop(); //取出队首状态 if(now.x==z||now.y==z) { printf("%d\n",now.step); exit(0); } extend(now); } printf("impossible\n");}int main(){ scanf("%d%d%d",&a,&b,&z); first.step=0; first.x=0; first.y=0; bfs(); return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。