[cpp] //九度OJ 教程87 廣度優先搜索之《非常可樂》 //http://ac.jobdu.com/problem.php?cid=1040&pid=86 #include <stdio.h> #define MAXS 110 #include <string.h> #include<queue> using namespace std; typedef struct E{ int a,b,c,t; }E; int mark[MAXS][MAXS][MAXS]; queue < E > Q; void AtoB(int &a,int sa,int &b,int sb) { int temp=sb-b; if(temp>a){b+=a;a=0;} else {a-=temp;b=sb;} } bool isok(E temp,int maxc) { maxc>>=1; return(temp.a==maxc&&temp.b==maxc||temp.a==maxc&&temp.c==maxc||temp.b==maxc&&temp.c==maxc); } int main() { int maxa,maxb,maxc; while(~scanf("%d %d %d",&maxc,&maxa,&maxb)&&maxc) { if(maxc&1){puts("NO");continue;} memset(mark,1,MAXS*MAXS*MAXS*sizeof(int)); while(Q.empty()==false)Q.pop(); E now,temp; int flag; now.a=now.b=now.t=0; now.c=maxc;flag=0; mark[0][0][maxc]=0; Q.push(now); while(Q.empty()==false&&flag==0) { now=Q.front(); Q.pop(); now.t++; temp=now; AtoB(temp.c,maxc,temp.b,maxb); if(mark[temp.a][temp.b][temp.c]) { mark[temp.a][temp.b][temp.c]=0; if(flag=isok(temp,maxc))break; Q.push(temp); } temp=now; AtoB(temp.a,maxa,temp.b,maxb); if(mark[temp.a][temp.b][temp.c]) { mark[temp.a][temp.b][temp.c]=0; if(flag=isok(temp,maxc))break; Q.push(temp); } temp=now; AtoB(temp.a,maxa,temp.c,maxc); if(mark[temp.a][temp.b][temp.c]) { mark[temp.a][temp.b][temp.c]=0; if(flag=isok(temp,maxc))break; Q.push(temp); } temp=now; AtoB(temp.b,maxb,temp.a,maxa); if(mark[temp.a][temp.b][temp.c]) { mark[temp.a][temp.b][temp.c]=0; if(flag=isok(temp,maxc))break; Q.push(temp); } temp=now; AtoB(temp.b,maxb,temp.c,maxc); if(mark[temp.a][temp.b][temp.c]) { mark[temp.a][temp.b][temp.c]=0; if(flag=isok(temp,maxc))break; Q.push(temp); } www.2cto.com temp=now; AtoB(temp.c,maxc,temp.a,maxa); if(mark[temp.a][temp.b][temp.c]) { mark[temp.a][temp.b][temp.c]=0; if(flag=isok(temp,maxc))break; Q.push(temp); } } if(flag)printf("%d\n",now.t); else puts("NO"); } return 0; }
