倒水问题学习小记 Poj 1606 + 3414 + Hdu 1495 + UVA 10603

梦里梦外; 2022-08-27 10:49 177阅读 0赞

倒水问题是一个很经典题目，问题的基本模型：

有三个分别装有a升水，b升水，c升水的量筒，其中a,b互质，c>b>a>0，现在c筒装满水，问能否在c筒中量出d升水(c>d>0)。若可以，给出方案。

这种题一般的解法是利用隐式图的BFS，对于三个瓶子的情况只需要二维数组判重即可，因为总水量一定，知道两个第三个自然确定。

参考资料：

[倒水问题的3个相关文章][3]

[倒水问题-CSDN论坛][-CSDN]

数学推导的最终结论：

"如果有n个壶容积分别为A1，A2，……，An（Ai均为大于0的整数）  
设w为另一大于0的整数。则用此n个壶可倒出w升水的充要条件为：  
1)w小于等于A1+A2+……+An；  
2)w可被(A1,A2,……,An)（这n个数的最大公约数）整除。"

**Zoj 1005 Jugs**

最简单的一道倒水问题，题意表明数据保证有解，并且没有要求给出最优解，所以直接暴力循环即可。

拿一个较小的瓶子一直往大的里面倒，当大瓶满的时候就倒空，当小瓶没有水的时候就加满，给出的数据A B是互素的，所以在题目给的前提下我们总是能给出可行解。

#include <cstdio>
    
    int main ()
    {
    	int ca,cb,n;
    	while (~scanf("%d%d%d",&ca,&cb,&n))
    	{
    		if (cb == n)
    		{
    			printf("fill B\nsuccess\n");
    			continue;
    		}
    		if (ca == n)
    		{
    			printf("fill A\n");
    			printf("pour A B\n");
    			printf("success\n");
    			continue;
    		}
    		int t=0;
    		while (t != n)//此时表示B中水的容量
    		{
    			printf("fill A\n");
    			printf("pour A B\n");
    			t+=ca;
    			if (t>cb)
    			{
    				t-=cb;
    				printf("empty B\n");
    				printf("pour A B\n");
    			}
    		}
    		printf("success\n");
    	}
    	return 0;
    }

**Poj 1606 Jugs**

和上面那题完全一样，尝试使用BFS的方法解决。

注：Zoj上那道题测试数据很弱，有些细节有错误的代码都可以AC，所以建议到Poj提交

Hdu 上也有一道一样的题，但貌似那题后台没有特判，所以还不知道AC的正确姿势……

//Poj 1606 c++ AC g++ RE
    #include <queue>
    #include <cstdio>
    #include <cstring>
    #include <string>
    #include <iostream>
    using namespace std;
    
    string markway[6]={"fill A","empty A","pour A B",
                         "fill B","empty B","pour B A"};
    
    const int N=1005;
    bool visit[N][N];
    int n,m,d;
    
    struct Point
    {
    	int x,y;
    };
    struct Path
    {
    	int rote;
    	Point p;
    }path[N][N];
    
    Point BFS ()
    {
    	memset(visit,false,sizeof(visit));
    	Point st,now[6];
    	st.x=st.y=0;
    	queue<Point >q;
    	q.push(st);
    	visit[st.x][st.y]=true;
    
    	while (!q.empty())
    	{
    		Point pre=q.front();
    		q.pop();
    		int i;
    		for (i=0;i<6;i++)
    			now[i]=pre;
    		now[0].x=n;  //倒满A
    		now[1].x=0;  //倒空A
    		now[3].y=m;  //倒满B
    		now[4].y=0;  //倒空B
    		
    		if (now[2].x>=m-now[2].y)  //将A倒入B
    			now[2].x-=(m-now[2].y),now[2].y=m;
    		else
    			now[2].y+=now[2].x,now[2].x=0;
    
    		if (now[5].y>=n-now[5].x)  //将B倒入A
    			now[5].y-=(n-now[5].x),now[5].x=n;
    		else
    			now[5].x+=now[5].y,now[5].y=0;
    
    		for (i=0;i<6;i++)
    		{
    			if (visit[now[i].x][now[i].y]==false)
    			{
    				visit[now[i].x][now[i].y]=true;
    				q.push(now[i]);
    				path[now[i].x][now[i].y].p=pre;
    				path[now[i].x][now[i].y].rote=i;
    			}
    			if (now[i].x==d || now[i].y==d)
    				return now[i];
    		}
    	}
    }
    
    void Output (Point post)
    {
    	if (post.x==0 && post.y==0)
    		return;
    	Output(path[post.x][post.y].p);
    	cout<<markway[path[post.x][post.y].rote]<<endl;
    	return ;
    }
    
    int main ()
    {
    	while (~scanf("%d%d%d",&n,&m,&d))
    	{
    		Point post=BFS();
    		Output(post);
    		printf("success\n");
    	}
    	return 0;
    }

**Poj 3414 Pots**

和前两题大同小异

注意判断无解

//c++AC g++RE
    #include <queue>
    #include <cstdio>
    #include <cstring>
    #include <string>
    #include <iostream>
    using namespace std;
    
    string markway[6]={"FILL(1)","DROP(1)","POUR(1,2)",
                         "FILL(2)","DROP(2)","POUR(2,1)"};
    
    const int N=105;
    bool visit[N][N];
    int n,m,d;
    
    struct Point
    {
    	int x,y;
    };
    
    struct Path
    {
    	int rote;
    	Point p;
    }path[N][N];
    
    Point BFS ()
    {
    	memset(visit,false,sizeof(visit));
    	queue<Point> Q;
    	Point st,now[6];
    	st.x=st.y=0;
    	Q.push(st);
    	visit[st.x][st.y]=true;
    
    	while (!Q.empty())
    	{
    		Point pre=Q.front();
    		Q.pop();
    		int i;
    		for (i=0;i<6;i++)
    			now[i]=pre;
    		now[0].x=n;  //倒满A
    		now[1].x=0;  //倒空A
    		now[3].y=m;  //倒满B
    		now[4].y=0;  //倒空B
    		
    		if (now[2].x>=m-now[2].y)  //将A倒入B
    			now[2].x-=(m-now[2].y),now[2].y=m;
    		else
    			now[2].y+=now[2].x,now[2].x=0;
    
    		if (now[5].y>=n-now[5].x)  //将B倒入A
    			now[5].y-=(n-now[5].x),now[5].x=n;
    		else
    			now[5].x+=now[5].y,now[5].y=0;
    
    		for (i=0;i<6;i++)
    		{
    			if (visit[now[i].x][now[i].y]==false)
    			{
    				visit[now[i].x][now[i].y]=true;
    				Q.push(now[i]);
    				
    				path[now[i].x][now[i].y].p=pre;
    				path[now[i].x][now[i].y].rote=i;
    			}
    			if (now[i].x==d || now[i].y==d)
    				return now[i];
    		}
    	}
    }
    
    void Output (Point post,int step)
    {
    	if (post.x==0 && post.y==0)
    	{
    		printf("%d\n",step);
    		return;
    	}
    	Output(path[post.x][post.y].p,step+1);
    	cout<<markway[path[post.x][post.y].rote]<<endl;
    	return ;
    }
    
    int Gcd (int x,int y)
    {
        return !y?x:Gcd(y,x%y);
    }
    
    int main ()
    {
    	scanf("%d%d%d",&n,&m,&d);
    	if (d%Gcd(n,m)!=0)
    		printf("impossible\n");
    	else
    		Output(BFS(),0);
    	return 0;
    }

**Hdu 1495 非常可乐**

这题要求平分，对于BFS做法稍加判断即可。

网上有大神找出了规律……代码附在后面

#include <queue>
    #include <cstdio>
    #include <cstring>
    #include <iostream>
    using namespace std;
    
    const int N=105;
    bool visit[N][N];
    int n,m,d;
    
    struct Point
    {
    	int x,y,step;
    };
    
    int BFS ()
    {
    	memset(visit,false,sizeof(visit));
    	queue<Point> Q;
    	Point st,now[6];
    	st.x=st.y=st.step=0;
    	Q.push(st);
    	visit[st.x][st.y]=true;
    
    	while (!Q.empty())
    	{
    		Point pre=Q.front();
    		Q.pop();
    		int i;
    		for (i=0;i<6;i++)
    		{
    			now[i]=pre;
    			now[i].step++;
    		}
    		now[0].x=n;  //倒满A
    		now[1].x=0;  //倒空A
    		now[3].y=m;  //倒满B
    		now[4].y=0;  //倒空B
    		
    		if (now[2].x>=m-now[2].y)  //将A倒入B
    			now[2].x-=(m-now[2].y),now[2].y=m;
    		else
    			now[2].y+=now[2].x,now[2].x=0;
    
    		if (now[5].y>=n-now[5].x)  //将B倒入A
    			now[5].y-=(n-now[5].x),now[5].x=n;
    		else
    			now[5].x+=now[5].y,now[5].y=0;
    
    		for (i=0;i<6;i++)
    		{
    			if (now[i].x==d/2)
    			{//当一个杯子分出一半水时,检查另一杯中是否有水
    				if (now[i].y==0) return now[i].step;
    				return now[i].step+1;
    			}
    			if (visit[now[i].x][now[i].y]==false)
    			{
    				visit[now[i].x][now[i].y]=true;
    				Q.push(now[i]);
    			}
    		}
    	}
    	return -1;
    }
    
    int Gcd (int x,int y)
    {
        return !y?x:Gcd(y,x%y);
    }
    
    int main ()
    {
    	while (~scanf("%d%d%d",&d,&n,&m),d)
    	{
    		int g=Gcd(n,m);
    		d/=g,n/=g,m/=g;
    		if (d%2==1)
    		{
    			printf("NO\n");
    			continue;
    		}
    		if (n==d/2 || m==d/2)
    		{
    			printf("1\n");
    			continue;
    		}
    		if (m>n) swap(n,m); //保证第一个杯子较大
    		int step=BFS();
    		printf("%d\n",step);
    	}
    	return 0;
    }

以下参考了  
  
http://acm.hdu.edu.cn/discuss/problem/post/reply.php?postid=17815&messageid=1&deep=0

#include <cstdio>
    
    int Gcd (int x,int y)
    {
        return !y?x:Gcd(y,x%y);
    }
    
    int main ()
    {
    	int a,b,c;
    	while (scanf("%d%d%d",&a,&b,&c),a)
    	{
    		int g=Gcd(b,c);
    		a /= g;
    		b /= g;
    		c /= g;
    		if (a & 1)
    			puts("NO");
    		else
    			printf("%d\n",a-1);
    	}
    	return 0;
    }

**UVA - 10603 Fill**

纠结的一题，到写这篇博文的时候我还没有过掉这题。。。。

目测这题的数据在今年被加强了，网上流传的许多不严谨代码都过不了了。

分析、简单测试数据、BFS代码参见：http://www.2cto.com/kf/201405/299036.html

p.s.我过了上面文章里的数据还是不能AC。。。

这题还可以用dp或最短路解决。

最短路建图：（a，b）这表示一个状态 ， 把每个这样的状态看成是一个点 ， 建图时 ， 就判断这个点可以到达哪些点 ， 如果能到达 ， 就连一条有向边 ， 边的权值为所倒水的多少。

参考题解：[uva 10603 状态压缩 最短路\_曾晨\_新浪博客][uva 10603 _]

[3]: http://www.douban.com/note/22317316/
[-CSDN]: http://bbs.csdn.net/topics/390539579
[uva 10603 _]: http://blog.sina.com.cn/s/blog_c0d5430b0101dx04.html