三个水杯 (bfs)

ゝ一世哀愁。 2022-06-18 01:56 155阅读 0赞

描述

给出三个水杯，大小不一，并且只有最大的水杯的水是装满的，其余两个为空杯子。三个水杯之间相互倒水，并且水杯没有标识，只能根据给出的水杯体积来计算。现在要求你写出一个程序，使其输出使初始状态到达目标状态的最少次数。

输入

第一行一个整数N(0<N<50)表示N组测试数据  
接下来每组测试数据有两行，第一行给出三个整数V1 V2 V3 (V1>V2>V3 V1<100 V3>0)表示三个水杯的体积。  
第二行给出三个整数E1 E2 E3 （体积小于等于相应水杯体积）表示我们需要的最终状态

输出

每行输出相应测试数据最少的倒水次数。如果达不到目标状态输出-1

样例输入

2
    6 3 1
    4 1 1
    9 3 2
    7 1 1

样例输出

3
    -1

写了很长时间 参考了这位博主http://blog.csdn.net/shengweisong/article/details/38466893?utm\_source=tuicool&utm\_medium=referral

假设杯子初始容积为6 3 1, 那么每个杯子初始水量为6 0 0 要倒成2 3 1这种状态如下:

注释:1->2代表第一个杯子往第二个杯子里倒水  3.3.0 代表1号杯水体积为3，2号体积为3，3号杯体积为0

初始水量为6 0 0  ———假设要倒成2 3 1的状态

1->2  3.3.01->3  5.0.1

2->1  2号为空2->3  2号为空

3->1  3号为空3->2  3号为空

6 0 0 出队 ——3 3 0 入队

1->2    2满1->3  2.3.1

2->1   6.0.02->3  3.2.1

3->1   3号为空3->2  3空

3 3 0 出队——5.0.1入队

1->2   2.3.11->3  3满

2->1  2空2->3  2空

3->1  6.0.03->2  5.1.0

5.0.1 出队———2.3.1入队

得到结果，倒水步骤为：6.0.0 ->3.3.0->2.3.1 共2步

代码：

#include<iostream>
    #include<algorithm>
    #include <cstdio>
    #include <string.h>
    #include <queue>
    using namespace std;
    struct st{
    	int tj[3];//体积  
    	int sl[3];//起始状态 第一个杯子满水，另外 两为空 
    	int mb[3];//目标状态 
    	int s;//步数 
    }zt;
    queue <struct st> Q;
    int v[101][101][101]={0};
    int bfs()
    {
    	int i,j,c;
    	memset(v,0,sizeof(v));
    	zt.s = 0; 
    	Q.push(zt);
    	v[zt.sl[0]][zt.sl[1]][zt.sl[2]] = 1;
    	while (!Q.empty())
    	{
    		struct st t = Q.front();
    		Q.pop();
    		if (t.sl[0] == zt.mb[0] && t.sl[1] == zt.mb[1] && t.sl[2] == zt.mb[2])
    		{
    			return t.s; //达到指定水量 
    		}
    		for (i=0; i<3; i++)
    		{
    			for (j=0; j<3; j++)
    			{
    				if (i!=j) //自己不能给自己
    				{
    					c = t.tj[j]-t.sl[j]; //用杯子体积减去当前杯子水量  这个杯子还可以放多少水
    					if (t.sl[i] < c) //如果可以放的水要比供水的还要多，那么就把供水的杯子水全部拿出 
    					 c = t.sl[i];
    					struct st vt;
    					vt = t;
    					vt.sl[i] -= c; //提供水的杯子 减去提供出去的水
    					vt.sl[j] += c; //接受水的，加上相应的水 
    					if (!v[vt.sl[0]][vt.sl[1]][vt.sl[2]])
    					{
    						vt.s = t.s+1;
    						Q.push(vt);
    						v[vt.sl[0]][vt.sl[1]][vt.sl[2]]=1;
    					}
    				 } 
    			}
    		}
    	} 
    	return -1;
    }
    int main()
    {
    	int n,i,j;
    	cin>>n;
    	while (n--)
    	{
    		while (!Q.empty())
    		{
    			Q.pop();
    		}
    		for (i=0; i<3; i++)
    		{
    			cin>>zt.tj[i]; //输入杯子体积 
    		}
    		for (i=0; i<3; i++)
    		{
    			cin>>zt.mb[i];//目标水量 
    		}
    		zt.sl[0] = zt.tj[0]; //第一个设为满的 
    		zt.sl[1] = 0; //空杯子 
    		zt.sl[2] = 0;
    		cout<<bfs()<<endl;
    	}
    return 0;
    }