hdu 1495 非常可乐
点击打开链接
大意：有三个杯子，开始时第一个杯子装满水（体积为a）。。。。倒来倒去，得到其中2个杯里的水的体积都为
a/2。。。。求最小次数。。。。不存在就输出NO。。。。
从图（以前都是图题）的点转化成状态（这题比较现实化）。。。。
struct point//a,b,c是某一状态下三个杯里装的水的体积。。。。v是从开始到该状态倒了多少次。。。。
{
int a, b, c, v;
};
在任意状态下（即每次的队头）。。。。都有6种倒法（即遍历6种）a->b,c。。。
b->a,c。。。。c->a,b。。。。。
#include"stdio.h"#include"string.h"#include"queue"using namespace std;bool v[111][111][111];struct node{int a,b,c,cnt;};void bfs(int a,int b,int c){queue<node>Q;node q,p;q.a=a;q.b=0;q.c=0;q.cnt=0;Q.push(q);memset(v,0,sizeof(v));while(!Q.empty()){q=Q.front();Q.pop();v[q.a][q.b][q.c]=1;if( (q.a==a/2&&q.b==a/2)|| (q.b==a/2&&q.c==a/2)|| (q.a==a/2&&q.c==a/2)){printf("%d\n",q.cnt);return ;}//a->其他if(q.a!=0){//a->bif(q.a>b-q.b)//倒完{p.a=q.a-(b-q.b);p.b=b;p.c=q.c;p.cnt=q.cnt+1;}else //倒不完{p.b=q.b+q.a;p.a=0;p.c=q.c;p.cnt=q.cnt+1;}if(!v[p.a][p.b][p.c]){v[p.a][p.b][p.c]=1;Q.push(p);}//a->cif(q.a>c-q.c)//倒完{p.a=q.a-(c-q.c);p.c=c;p.b=q.b;p.cnt=q.cnt+1;}else//倒不完{p.c=q.c+q.a;p.a=0;p.b=q.b;p.cnt=p.cnt+1;}if(!v[p.a][p.b][p.c]){v[p.a][p.b][p.c]=1;Q.push(p);}}if(q.b!=0)//b到其他{//b->a;if(q.b>a-q.a)//倒不完{p.b=q.b-(a-q.a);p.a=a;p.c=q.c;p.cnt=q.cnt+1;}else//倒完{p.a=q.a+q.b;p.b=0;p.c=q.c;p.cnt=q.cnt+1;}if(!v[p.a][p.b][p.c]){v[p.a][p.b][p.c]=1;Q.push(p);}//b->c;if(q.b>c-q.c)//倒不完{p.b=q.b-(c-q.c);p.c=c;p.a=q.a;p.cnt=q.cnt+1;}else//倒完{p.c=q.c+q.b;p.b=0;p.a=q.a;p.cnt=q.cnt+1;}if(!v[p.a][p.b][p.c]){v[p.a][p.b][p.c]=1;Q.push(p);}}if(q.c!=0)//c到其他{//c->a;if(q.c>a-q.a)//倒不完{p.c=q.c-(a-q.a);p.a=a;p.b=q.b;p.cnt=q.cnt+1;if(!v[p.a][p.b][p.c]){v[p.a][p.b][p.c]=1;Q.push(p);}}else//倒完{p.a=q.a+q.c;p.c=0;p.b=q.b;p.cnt=q.cnt+1;if(!v[p.a][p.b][p.c]){v[p.a][p.b][p.c]=1;Q.push(p);}}//c->bif(q.c>b-q.b)//倒不完{p.c=q.c-(b-q.b);p.b=b;p.a=q.a;p.cnt=q.cnt+1;if(!v[p.a][p.b][p.c]){v[p.a][p.b][p.c]=1;Q.push(p);}}else//倒完{p.b=q.b+q.c;p.c=0;p.a=q.a;p.cnt=q.cnt+1;if(!v[p.a][p.b][p.c]){v[p.a][p.b][p.c]=1;Q.push(p);}}}}puts("NO");return ;}int main(){int a,b,c;while(scanf("%d%d%d",&a,&b,&c)!=EOF){if(a==0&&b==0&&c==0)break;if(a%2==1)printf("NO\n");else bfs(a,b,c);}return 0;}