非常可乐
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 4142 Accepted Submission(s): 1691
Problem Description
大家一定觉的运动以后喝可乐是一件很惬意的事情，但是seeyou却不这么认为。因为每次当seeyou买了可乐以后，阿牛就要求和seeyou一起分享这一瓶可乐，而且一定要喝的和seeyou一样多。但seeyou的手中只有两个杯子，它们的容量分别是N 毫升和M 毫升 可乐的体积为S （S<101）毫升 (正好装满一瓶) ，它们三个之间可以相互倒可乐 (都是没有刻度的，且 S==N+M，101＞S＞0，N＞0，M＞0) 。聪明的ACMER你们说他们能平分吗？如果能请输出倒可乐的最少的次数，如果不能输出"NO"。
Input
三个整数 : S 可乐的体积 , N 和 M是两个杯子的容量，以"0 0 0"结束。
Output
如果能平分的话请输出最少要倒的次数，否则输出"NO"。
Sample Input
7 4 3
4 1 3
0 0 0
Sample Output
NO
3
Author
seeyou
Source
Recommend
LL | We have carefully selected several similar problems for you:
1 //203MS 4880K 2201 B G++ 2 /* 3 4 题意： 5 互倒可乐，是否可以平分 6 7 BFS： 8 比较基本的bfs，难点在状态分析，每一步可以有六种走法，直接暴力即可， 9 然后用vis数组来标记重复的，以免TLE。 10 11 */12 #include13 #include 14 using namespace std;15 struct node{16 int s,n,m;17 int step;18 };19 int vis[105][105][105];20 int bfs(int s,int n,int m)21 {22 memset(vis,0,sizeof(vis));23 vis[s][0][0]=1;24 node t={s,0,0,0};25 queue Q;26 Q.push(t);27 while(!Q.empty()){28 t=Q.front();29 Q.pop();30 //printf("%d %d %d\n",t.s,t.n,t.m);31 if(t.s==t.n && t.m==0) return t.step;32 t.step++;33 if(s-t.s>t.n && !vis[t.s+t.n][0][t.m]){34 node tt=t;35 tt.s=t.s+t.n;tt.n=0;vis[tt.s][0][tt.m]=1;36 Q.push(tt); 37 }38 if(s-t.s>t.m && !vis[t.s+t.m][t.n][0]){39 node tt=t;40 tt.s=t.s+t.m;tt.m=0;vis[tt.s][tt.n][0]=1;41 Q.push(tt);42 }43 if(n-t.n<=t.s && !vis[t.s-(n-t.n)][n][t.m]){44 node tt=t;45 tt.s-=(n-t.n);tt.n=n;vis[tt.s][tt.n][tt.m]=1;46 Q.push(tt);47 }48 if(n-t.n>t.m && !vis[t.s][t.n+t.m][0]){49 node tt=t;50 tt.n+=t.m;tt.m=0;vis[tt.s][tt.n][0]=1;51 Q.push(tt);52 }else if(n-t.n<=t.m && !vis[t.s][n][t.m-(n-t.n)]){53 node tt=t;54 tt.n=n;tt.m-=(n-t.n);vis[tt.s][tt.n][tt.m]=1;55 Q.push(tt);56 }57 if(m-t.m<=t.s && !vis[t.s-(m-t.m)][t.n][m]){58 node tt=t;59 tt.m=m;tt.s-=(m-t.m);vis[tt.s][tt.n][m]=1;60 Q.push(tt);61 }62 if(m-t.m>t.n && !vis[t.s][0][t.m+t.n]){63 node tt=t;64 tt.n=0;tt.m+=t.n;vis[tt.s][0][tt.m]=1;65 Q.push(tt);66 }else if(m-t.m<=t.n && !vis[t.s][t.n-(m-t.m)][m]){67 node tt=t;68 tt.n-=(m-t.m);tt.m=m;vis[tt.s][tt.n][tt.m]=1;69 Q.push(tt);70 }71 } 72 return 0;73 }74 int main(void) 75 {76 int s,n,m;77 while(scanf("%d%d%d",&s,&n,&m),s+n+m)78 {79 if(s&1){80 puts("NO");continue;81 }82 if(n==m){83 puts("1");continue;84 }85 if(m>n){86 int t=m;m=n;n=t;87 }88 int ans=bfs(s,n,m);89 if(ans) printf("%d\n",ans);90 else puts("NO");91 }92 return 0;93 }