Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 25498 Accepted Submission(s):
9921
#include<queue> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int n,m,s,f; int vis[102][102][102]; void bfs(){ memset(vis,0,sizeof(vis)); queue<int>que1,que2,que3,step; que1.push(0);que2.push(s); que3.push(0);step.push(0); vis[0][s][0]=1; while(!que1.empty()){ int now1=que1.front();que1.pop(); int now2=que2.front();que2.pop(); int now3=que3.front();que3.pop(); int nows=step.front();step.pop(); if(now1==s/2&&(now2==0||now3==0)){ printf("%d\n",nows);f=1; break; } if(now2==s/2&&(now1==0||now3==0)){ printf("%d\n",nows);f=1; break; } if(now3==s/2&&(now1==0||now2==0)){ printf("%d\n",nows);f=1; break; } if(now1!=0){ if(!vis[0][now2+now1][now3]){ vis[0][now2+now1][now3]=1; que1.push(0);que2.push(now2+now1); que3.push(now3);step.push(nows+1); } int c3=now3+now1,c1=0; if(c3>=m){ c1=c3-m;c3=m; } if(!vis[c1][now2][c3]){ vis[c1][now2][c3]=1; que1.push(c1);que2.push(now2); que3.push(c3);step.push(nows+1); } } if(now2!=0){ int c1=now2+now1,c2,c3; if(c1>n){ c2=c1-n;c1=n; } else c2=0; if(!vis[c1][c2][now3]){ vis[c1][c2][now3]=1; que1.push(c1);que2.push(c2); que3.push(now3);step.push(nows+1); } c3=now2+now3,c2; if(c3>n){ c2=c3-m;c3=m; } else c2=0; if(!vis[now1][c2][c3]){ vis[now1][c2][c3]=1; que1.push(now1);que2.push(c2); que3.push(c3);step.push(nows+1); } } if(now3!=0){ if(!vis[now1][now2+now3][0]){ vis[now1][now2+now3][0]=1; que1.push(now1);que2.push(now2+now3); que3.push(0);step.push(nows+1); } int c1=now1+now3,c3=0; if(c1>=n){ c3=c1-n;c1=n; } if(!vis[c1][now2][c3]){ vis[c1][now2][c3]=1; que1.push(c1);que2.push(now2); que3.push(c3);step.push(nows+1); } } } } int main(){ //freopen("lpp.in","r",stdin); //freopen("lpp.out","w",stdout); while(scanf("%d%d%d",&s,&n,&m)&&s!=0&&n!=0&&m!=0){ if(s&1){ printf("NO\n");continue; } f=0;bfs();if(f==0){ printf("NO\n");continue; } } }
原文:https://www.cnblogs.com/cangT-Tlan/p/9910981.html