题目连接:http://59.69.128.200/JudgeOnline/problem.php?pid=21
题意:给三个容量不同的水杯,其中最大的那个水杯中装满水,然后三个杯子相互倒水,问从初始状态到目的状态至少要多少次。
解题思路:由于每次只能想其中一个杯子中倒水,并且,而且每次当前杯子中的水倒完,或者是将另一个杯子倒满为止。相当于从一个点到另一个点。
因此每次选择一个杯子向另外两个杯子倒水(除非倒水的杯子没有水)
#include<iostream> #include<queue> #include<memory.h> #include<algorithm> using namespace std; int flat; int v[103][103]; int x,y,z,p,q,r; struct A {int a,b,c;}m,k; int main() { /*freopen("1.txt","r",stdin);*/ int n;cin>>n; while(n--) { cin>>x>>y>>z;cin>>p>>q>>r; queue<A> s,t;m.a=x;m.b=0;m.c=0;s.push(m); flat=0;int sum=0; memset(v,0,sizeof(v)); while(1) { sum++; while(!s.empty()) { k=s.front(); m=s.front();int f1=x-m.a;int f2=y-m.b;int f3=z-m.c; v[k.b][k.c]=1; if(k.a==p&&k.b==q&&k.c==r){flat=1;break;} if(f1>0) { if(f1>=k.b&&!v[0][k.c]){m.a=k.a+k.b;m.b=0;m.c=k.c;t.push(m);} else if(f1<k.b&&!v[k.b-f1][k.c]){m.a=x;m.b=k.b-f1;m.c=k.c;t.push(m);} if(f1>=k.c&&!v[k.b][0]){m.a=k.a+k.c;m.b=k.b;m.c=0;t.push(m);} else if(f1<k.c&&!v[k.b][k.c-f1]){m.a=x;m.b=k.b;m.c=k.c-f1;t.push(m);} } if(f2>0) { if(f2>=k.a&&!v[k.b+k.a][k.c]){m.a=0;m.b=k.a+k.b;m.c=k.c;t.push(m);} else if(f2<k.a&&!v[y][k.c]){m.a=k.a-f2;m.b=y;m.c=k.c;t.push(m);} if(f2>=k.c&&!v[k.b+k.c][0]){m.a=k.a;m.b=k.b+k.c;m.c=0;t.push(m);} else if(f2<k.c&&!v[y][k.c-f2]){m.a=k.a;m.b=y;m.c=k.c-f2;t.push(m);}; } if(f3>0) { if(f3>=k.a&&!v[k.b][k.c+k.a]){m.a=0;m.b=k.b;m.c=k.c+k.a;t.push(m);} else if(f3<k.a&&!v[k.b][z]){m.a=k.a-f3;m.b=k.b;m.c=z;t.push(m);} if(f3>=k.b&&!v[0][k.c+k.b]){m.a=k.a;m.b=0;m.c=k.c+k.b;t.push(m);} else if(f3<k.b&&!v[k.b-f3][z]){m.a=k.a;m.b=k.b-f3;m.c=z;t.push(m);}; } s.pop(); } if(flat) break; else { if(t.empty()) break; while(!t.empty()) { s.push(t.front());t.pop(); } } } if(flat) cout<<sum-1<<endl; else cout<<"-1"<<endl; } }