HDU 1495 非常可乐

非常可乐Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2874 Accepted Submission(s): 1157


Problem DescriptionInputOutputSample InputSample OutputAuthorSourceRecommend#include<iostream>#include<cstring>#include<queue>using namespace std;bool visit[105][105][105];typedef struct cola{int a,b,c,v;cola(){a=b=c=v=0;}};bool pre(cola x,int y){if(x.a==y/2&&x.b==y/2||x.c==y/2&&x.a==y/2||x.c==y/2&&x.b==y/2)return true;return false;}int BFS(cola x,int a,int b,int k){cola now,temp;queue<cola> c;c.push(x);while(!c.empty()){now=c.front();c.pop();if(now.b<a&&now.a>0){temp.c=now.c;temp.v=now.v+1;if(now.a>a-now.b){temp.a=now.a+now.b-a;temp.b=a;}else{temp.b=now.b+now.a;temp.a=0;}if(pre(temp,k))return temp.v;if(!visit[temp.a][temp.b][temp.c]){visit[temp.a][temp.b][temp.c]=true;c.push(temp);}}if(now.c<b&&now.a>0){temp.v=now.v+1;temp.b=now.b;if(now.a>b-now.c){temp.a=now.a+now.c-b;temp.c=b;}else{temp.c=now.c+now.a;temp.a=0;}if(pre(temp,k))return temp.v;if(!visit[temp.a][temp.b][temp.c]){visit[temp.a][temp.b][temp.c]=true;c.push(temp);}}if(now.a<k&&now.b>0){temp.c=now.c;temp.v=now.v+1;if(now.b>k-now.a){temp.b=now.b+now.a-k;temp.a=k;}else{temp.a=now.a+now.b;temp.b=0;}if(pre(temp,k))return temp.v;if(!visit[temp.a][temp.b][temp.c]){visit[temp.a][temp.b][temp.c]=true;c.push(temp);}}if(now.c<b&&now.b>0){temp.a=now.a;temp.v=now.v+1;if(now.b>b-now.c){temp.b=now.b+now.c-b;temp.c=b;}else{temp.c=now.c+now.b;temp.b=0;}if(pre(temp,k))return temp.v;if(!visit[temp.a][temp.b][temp.c]){visit[temp.a][temp.b][temp.c]=true;c.push(temp);}}if(now.a<k&&now.c>0){temp.b=now.b;temp.v=now.v+1;if(now.c>k-now.a){temp.c=now.c+now.a-k;temp.a=k;}else{temp.a=now.a+now.c;temp.c=0;}if(pre(temp,k)) return temp.v;if(!visit[temp.a][temp.b][temp.c]){visit[temp.a][temp.b][temp.c]=true;c.push(temp);}}if(now.b<a&&now.c>0){temp.a=now.a;temp.v=now.v+1;if(now.c>a-now.b){temp.c=now.c+now.b-a;temp.b=a;}else{temp.b=now.b+now.c;temp.c=0;}if(pre(temp,k))return temp.v;if(!visit[temp.a][temp.b][temp.c]){visit[temp.a][temp.b][temp.c]=true;c.push(temp);}}}return -1;}int main(){int p,q,r,ans;cola ini;while(scanf("%d%d%d",&p,&q,&r)){if(p==0&&q==0&&r==0)break;if(p%2){printf("NO\n");continue;}if(q==r){printf("1\n");continue;}memset(visit,false,sizeof(visit));ini.a=p;ini.b=0;ini.c=0;visit[p][0][0]=true;ans=BFS(ini,q,r,p);if(ans==-1)printf("NO\n");elseprintf("%d\n",ans);}return 0;}