首页 > 代码库 > [Wikioi 1226]倒水问题

[Wikioi 1226]倒水问题

2024-07-05 20:33:10   224人阅读

题目描述 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桶
每种策略在判断条件后模拟一遍就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;}

 


联系
我们