三个水杯
时间限制：1000 ms | 内存限制：65535 KB
难度：4
描述
给出三个水杯，大小不一，并且只有最大的水杯的水是装满的，其余两个为空杯子。三个水杯之间相互倒水，并且水杯没有标识，只能根据给出的水杯体积来计算。现在要求你写出一个程序，使其输出使初始状态到达目标状态的最少次数。
输入
第一行一个整数N(0<N<50)N(0<N<50)表示N组测试数据
接下来每组测试数据有两行，第一行给出三个整数V1 V2 V3 (V1>V2>V3V1<100V3>0)(V1>V2>V3V1<100V3>0)表示三个水杯的体积。
第二行给出三个整数E1 E2 E3 （体积小于等于相应水杯体积）表示我们需要的最终状态
输出
每行输出相应测试数据最少的倒水次数。如果达不到目标状态输出-1
样例输入
2
6 3 1
4 1 1
9 3 2
7 1 1
样例输出
3
-1
第一次做广搜，参考别人的写的。用广搜的原因是每个杯子只能向其他两个杯子倒水，不能像自己倒水，就像树一样，走根节点走向子节点。
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
int v[4],e[4];
bool visit[101][101][101];//用于剪枝,visited[2][3][4]=true用来标记第1个杯子装2单位水，
//第2个杯子装3单位水，第3个杯子装4单位水已经访问过，
//以后遇到这种情况不用入队列了
typedef struct
{
int state[4];//用来保存三个杯子中的水的状态——state[1]的值代表第一个水杯的状态 ...
int setp;
}N;
//第i个杯子向第k个杯子倒水
void pour_Water(int i,int k,N& n)
{
if(n.state[i]<=v[k]-n.state[k])//如果第i个杯子中水的量小于k杯子的目标容量减去k杯子中现在的水量
{
n.state[k]+=n.state[i];
n.state[i]=0;
}
else
{
n.state[i]-=(v[k]-n.state[k]);
n.state[k]=v[k];
}
}
void BFS()
{
queue<N> q;
N start,next;
memset(visit,false,sizeof(visit));//标记每种状态的情况都没出现过
//初始化刚开始的状态，就是把第一个杯子得水装满，其余两个杯子不装水
start.setp=0;
start.state[1]=v[1];
start.state[2]=start.state[3]=0;
visit[start.state[1]][start.state[2]][start.state[3]]=true;
q.push(start);
while(!q.empty())
{
//如果满足目标状态，就可以退出。
if(next.state[1]==e[1]&&next.state[2]==e[2]&&next.state[3]==e[3])
{
cout<<next.setp<<endl;
return ;
}
next=q.front();//把队头元素取出来
q.pop();
N temp;
for(int i=0;i<3;i++)
for(int j=1;j<3;j++)//相当于以某个节点为根节点按层遍历，即bfs
{
//此式子可以保证当i+1为1时，k+1取2,3
//i+1=2时,k+1=1,3;i+1=3时,k+1=1,2
int k=(i+j)%3;
temp=next;//next杯子倒水，结果储存在temp中 ，
pour_Water(i+1,k+1,temp);
temp.setp+=1;
//如果此时三个杯中的水的状态没有出现过，把这种状态入队
if(!visit[temp.state[1]][temp.state[2]][temp.state[3]])
{
visit[temp.state[1]][temp.state[2]][temp.state[3]]=true;
q.push(temp);
}
}
}
//所有水杯的状态都进过队且没有一个满足目标状态的，
cout<<"-1"<<endl;
return ;
}
int main()
{
int n;
cin>>n;
while(n--)
{
cin>>v[1]>>v[2]>>v[3];
cin>>e[1]>>e[2]>>e[3];
BFS();
}
return 0;
}