HDU - 1495 非常可乐（bfs）
非常可乐
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 20347 Accepted Submission(s): 8248
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
<center> Statistic | Submit | Discuss | Note </center> 思路：a可以往b中倒水，可以往c倒。。。。总共有六种情况，BFS广度搜索就行了
注意搜索的时候要标记一下状态，用visit，不然会queue会超限。
就是代码有点多，要仔细。。。
网上大佬用数学方法做的orz。。。。https://blog.csdn.net/v5zsq/article/details/52097459，看不懂啊。
1 #include <iostream> 2 #include <cstdio> 3 #include <queue> 4 #include <cstring> 5 6 using namespace std; 7 8 typedef struct info{ 9 int a,b,c; 10 int countt; 11 }cup; 12 13 int s,m,n; 14 cup c1; 15 cup now,nextt; 16 int visit[105][105][105]; 17 18 19 int bfs(cup c){ 20 // while(!q.empty()){ 21 // q.pop(); 22 // } 23 queue<cup> q; 24 q.push(c); 25 while(!q.empty()){ 26 now=q.front(); q.pop(); 27 28 if((now.a==s/2&&now.b==s/2)||(now.a==s/2&&now.c==s/2)||(now.b==s/2&&now.c==s/2)){ 29 return now.countt; 30 } 31 if(now.a!=0){//第一个杯子向其他两个倒水 32 int vol=n-now.b; 33 if(vol!=0){ 34 if(now.a>=vol){ 35 nextt.b=n; 36 nextt.a=now.a-vol; 37 nextt.c=now.c; 38 nextt.countt=now.countt+1; 39 }else{ 40 nextt.b=now.b+now.a; 41 nextt.a=0; 42 nextt.c=now.c; 43 nextt.countt=now.countt+1; 44 } 45 if(!visit[nextt.a][nextt.b][nextt.c]){ 46 visit[nextt.a][nextt.b][nextt.c]=1; 47 q.push(nextt); 48 } 49 } 50 51 vol=m-now.c; 52 if(vol!=0){ 53 if(now.a>=vol){ 54 nextt.c=m; 55 nextt.a=now.a-vol; 56 nextt.b=now.b; 57 nextt.countt=now.countt+1; 58 q.push(nextt); 59 }else{ 60 nextt.c=now.c+now.a; 61 nextt.a=0; 62 nextt.b=now.b; 63 nextt.countt=now.countt+1; 64 } 65 if(!visit[nextt.a][nextt.b][nextt.c]){ 66 visit[nextt.a][nextt.b][nextt.c]=1; 67 q.push(nextt); 68 } 69 } 70 } 71 72 if(now.b!=0){//第二个杯子忘其他两个倒水 73 int vol=s-now.a; 74 if(vol!=0){ 75 if(now.b>=vol){ 76 nextt.a=s; 77 nextt.b=now.b-vol; 78 nextt.c=now.c; 79 nextt.countt=now.countt+1; 80 }else{ 81 nextt.a=now.a+now.b; 82 nextt.b=0; 83 nextt.c=now.c; 84 nextt.countt=now.countt+1; 85 } 86 if(!visit[nextt.a][nextt.b][nextt.c]){ 87 visit[nextt.a][nextt.b][nextt.c]=1; 88 q.push(nextt); 89 } 90 } 91 92 vol=m-now.c; 93 if(vol!=0){ 94 if(now.b>=vol){ 95 nextt.c=m; 96 nextt.a=now.a; 97 nextt.b=now.b-vol; 98 nextt.countt=now.countt+1; 99 }else{ 100 nextt.c=now.c+now.b; 101 nextt.b=0; 102 nextt.a=now.a; 103 nextt.countt=now.countt+1; 104 } 105 if(!visit[nextt.a][nextt.b][nextt.c]){ 106 visit[nextt.a][nextt.b][nextt.c]=1; 107 q.push(nextt); 108 } 109 } 110 } 111 112 if(now.c!=0){//第三个杯子忘其他两个倒水 113 int vol=s-now.a; 114 if(vol!=0){ 115 if(now.c>=vol){ 116 nextt.a=s; 117 nextt.c=now.c-vol; 118 nextt.b=now.b; 119 nextt.countt=now.countt+1; 120 }else{ 121 nextt.a=now.a+now.c; 122 nextt.c=0; 123 nextt.b=now.b; 124 nextt.countt=now.countt+1; 125 } 126 if(!visit[nextt.a][nextt.b][nextt.c]){ 127 visit[nextt.a][nextt.b][nextt.c]=1; 128 q.push(nextt); 129 } 130 } 131 132 vol=n-now.b; 133 if(vol!=0){ 134 if(now.c>=vol){ 135 nextt.b=n; 136 nextt.c=now.c-vol; 137 nextt.a=now.a; 138 nextt.countt=now.countt+1; 139 }else{ 140 nextt.b=now.b+now.c; 141 nextt.c=0; 142 nextt.a=now.a; 143 nextt.countt=now.countt+1; 144 } 145 if(!visit[nextt.a][nextt.b][nextt.c]){ 146 visit[nextt.a][nextt.b][nextt.c]=1; 147 q.push(nextt); 148 } 149 } 150 } 151 } 152 return 0; 153 } 154 155 int main() 156 { 157 while(~scanf("%d %d %d",&s,&n,&m)){ 158 memset(visit,0,sizeof(visit)); 159 if(s==0&&m==0&&n==0){break;} 160 if(m==n){ 161 printf("1\n"); 162 }else if(s&1==1){ 163 printf("NO\n"); 164 }else{ 165 c1.a=s; c1.b=0; c1.c=0; c1.countt=0; 166 int countt=bfs(c1); 167 if(countt==0){ 168 printf("NO\n"); 169 }else{ 170 printf("%d\n",countt); 171 } 172 } 173 } 174 return 0; 175 }
Momenta公司福利 286人发布
