Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 14153 Accepted Submission(s): 5653
1 #include <bits/stdc++.h> 2 using namespace std; 3 int gcd(int a,int b) 4 { 5 return b==0?a:gcd(b,a%b); 6 } 7 int main() 8 { 9 int a,b,c; 10 while(cin>>a>>b>>c&&(a&&b&&c)) 11 { 12 a/=gcd(b,c); 13 if(a&1) 14 cout<<"NO"<<endl; 15 else 16 cout<<a-1<<endl; 17 } 18 return 0; 19 }
给出BFS解法吧
分析：
这题代码有150行 但是基本是六中情况的重复了
1 #include<cstdio> 2 #include<cstring> 3 #include<queue> 4 using namespace std; 5 int v[5]; 6 int sign[110][110][100]; 7 struct cup//记录遍历中3个水杯容藏可乐情况 8 { 9 int v[5]; 10 int step; 11 }temp; 12 13 void pour(int a,int b)//倒水函数，把a杯子中的可乐倒到b杯子中 14 { 15 int sum=temp.v[a]+temp.v[b]; 16 if(sum>=v[b]) 17 temp.v[b]=v[b]; 18 else 19 temp.v[b]=sum; 20 temp.v[a]=sum-temp.v[b]; 21 } 22 23 void bfs() 24 { 25 int i,j; 26 queue<cup>q; 27 cup cnt; 28 cnt.v[1]=v[1]; 29 cnt.v[2]=0; 30 cnt.v[3]=0; 31 cnt.step=0; 32 q.push(cnt); 33 memset(sign,0,sizeof(sign)); 34 sign[v[1]][0][0]=1; 35 while(!q.empty()) 36 { 37 cnt=q.front(); 38 q.pop(); 39 if(cnt.v[1]==cnt.v[3]&&cnt.v[2]==0) 40 { 41 printf("%d\n",cnt.step); 42 return ; 43 } 44 for(i=1;i<4;++i) 45 { 46 for(j=1;j<4;++j) 47 { 48 if(i!=j)//自己不倒水给自己 49 { 50 temp=cnt;//每个水位情况都要把所有操作枚举一遍，所以都要赋值为原始水位情况 51 pour(i,j); 52 if(!sign[temp.v[1]][temp.v[2]][temp.v[3]]) 53 { 54 temp.step++; 55 q.push(temp); 56 sign[temp.v[1]][temp.v[2]][temp.v[3]]=1; 57 } 58 } 59 } 60 } 61 } 62 printf("NO\n"); 63 } 64 65 int main() 66 { 67 while(scanf("%d%d%d",&v[1],&v[2],&v[3])&&v[1]||v[2]||v[3]) 68 { 69 if(v[2]>v[3]) 70 { 71 int t=v[2]; 72 v[2]=v[3]; 73 v[3]=t; 74 } 75 bfs(); 76 } 77 return 0; 78 }
原文：http://www.cnblogs.com/ECJTUACM-873284962/p/6750320.html