描述
给三个杯子，大小不一，只有最大的杯子里装满了水，剩下的两个是空杯子。三个杯子相互倒水，杯子没有标记，只能根据给定的杯子的体积来计算。现在你需要写一个程序来输出最初的状态。
输入
一行整数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://acm.nyist.net/JudgeOnline/problem.php?pid=21六种状态0->1,1->0,1->2,2->1,2->3,3->2
#include<iostream> #include<cstdio> #include<cstring> #include<queue> using namespace std; int e1,e2,e3; struct node { int step; int v[3]; }; int cap[4]; bool vis[105][105][105]; void pour(int dest,int sour,node& t) { int water=cap[dest]-t.v[dest]; if(t.v[sour]<=water) { t.v[dest]+=t.v[sour]; t.v[sour]=0; } else { t.v[dest]+=water; t.v[sour]-=water; } } int bfs() { node s; s.v[0]=cap[0];s.v[1]=0;s.v[2]=0; s.step=0; vis[cap[0]][0][0]=true; queue<node>q; q.push(s); while(!q.empty()) { node tmp=q.front(); q.pop(); if(tmp.v[0]==e1&&tmp.v[1]==e2&&tmp.v[2]==e3)return tmp.step; for(int i=0;i<3;i++) { for(int j=1;j<3;j++) { int k=(i+j)%3;//模拟三种状态 if(tmp.v[i]==0||tmp.v[k]>=cap[k])continue; node x=tmp; pour(k,i,x); // cout<<x.v[0]<<x.v[1]<<x.v[2]<<endl; x.step=tmp.step+1; if(!vis[x.v[0]][x.v[1]][x.v[2]]) { vis[x.v[0]][x.v[1]][x.v[2]]=true; q.push(x); } } } } return -1; } int main() { int ca; scanf("%d",&ca); while(ca--) { for(int i=0;i<3;i++) { scanf("%d",&cap[i]); } scanf("%d%d%d",&e1,&e2,&e3); if(e1==cap[0]&&cap[1]==0&&cap[2]==0) { printf("0\n"); continue; } memset(vis,false,sizeof(vis)); int res=bfs(); printf("%d\n",res); } return 0; }