hdoj 1495 非常可乐(bfs)

非常可乐

**Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 7194 Accepted Submission(s): 2865
**

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

平分可乐,不能剩.

奇数的话直接no

偶数的话bfs

妈蛋写了140+行,简直令人感动.

然后一直WA

郁闷了好久,结果今天一看,竟然已经A了...

是测评傲娇了嘛2333

  1 
  2
  3    
  4    /*************************************************************************
  5    	> File Name: code/2015summer/searching/M.cpp
  6    	> Author: 111qqz
  7    	> Email: rkz2013@126.com 
  8    	> Created Time: 2015年07月25日 星期六 15时54分19秒
  9     ************************************************************************/
 10    
 11    #include<iostream>
 12    #include<iomanip>
 13    #include<cstdio>
 14    #include<algorithm>
 15    #include<cmath>
 16    #include<cstring>
 17    #include<string>
 18    #include<map>
 19    #include<set>
 20    #include<queue>
 21    #include<vector>
 22    #include<stack>
 23    #define y0 abc111qqz
 24    #define y1 hust111qqz
 25    #define yn hez111qqz
 26    #define j1 cute111qqz
 27    #define tm crazy111qqz
 28    #define lr dying111qqz
 29    using namespace std;
 30    #define REP(i, n) for (int i=0;i<int(n);++i)  
 31    typedef long long LL;
 32    typedef unsigned long long ULL;
 33    const int N=1E2+2;
 34    int s,m,n;
 35    int a[10];
 36    int lim[10];
 37    int f[5][5];
 38    int d[N][N][N];
 39    int ans;
 40    void bfs()
 41    {
 42        queue<int>q[10];
 43        memset(d,-1,sizeof(d));
 44        q[0].push(s);
 45        q[1].push(0);
 46        q[2].push(0);
 47        d[s][0][0]=0;
 48        int ne[4];
 49        memset(ne,0,sizeof(ne));
 50        while (!q[1].empty()&&!q[2].empty())
 51        {
 52    	  int p[3];
 53    	  p[0]=q[0].front();q[0].pop();
 54    	  p[1]=q[1].front();q[1].pop();
 55    	  p[2]=q[2].front();q[2].pop();
 56    	 // cout<<p[0]<<" "<<p[1]<<" "<<p[2]<<"d:"<<d[p[0]][p[1]][p[2]]<<endl;;
 57    	  for ( int i = 0 ;  i < 3  ; i++ )
 58    	  {
 59    		if (p[i]==0) continue;
 60    		for ( int j = i+1  ;  j < 3 ; j++ )
 61    		{
 62    		
 63    		    if (p[i]==p[j]&&p[i]+p[j]==s)
 64    		    {
 65    			 // cout<<"fufffffffffffffffffffffffff"<<endl;
 66    			  ans = d[p[0]][p[1]][p[2]];
 67    			//  cout<<"ans:"<<ans<<endl;
 68    			  return;
 69    		    }
 70    		}
 71    	  }
 72    	  for ( int i = 0  ; i < 3 ; i++ )   //i往j里倒
 73    	  {
 74    		if (p[i]==0) continue;  //为空时不能往其他里倒
 75    		for ( int j = 0 ;  j < 3 ; j++ )
 76    		{
 77    	  
 78    		    if(i==j)continue;//不能自己往倒给自己
 79    		    if (p[j]==lim[j]) continue;//被倒的为满时不能倒入
 80    		    if (p[i]+p[j]<=lim[j])//可以完全倒入
 81    		    {
 82    			  int k = f[i][j];
 83    			  ne[i]=0;
 84    			  ne[j]=p[i]+p[j];
 85    			  ne[k]=p[k];
 86    			  if (d[ne[0]][ne[1]][ne[2]]!=-1) continue;  //出现重复
 87    			  q[i].push(0);
 88    			  q[j].push(p[i]+p[j]);
 89    			  q[k].push(p[k]);
 90    			  d[ne[0]][ne[1]][ne[2]]=d[p[0]][p[1]][p[2]]+1;
 91    		    }
 92    		    else  // 不能完全倒入
 93    		    {
 94    			  int k = f[i][j];
 95    			  ne[i]=p[i]-(lim[j]-p[j]);
 96    			  ne[j]=lim[j];
 97    			  ne[k]=p[k];
 98    			  if (d[ne[0]][ne[1]][ne[2]]!=-1) continue; //出现重复
 99    			  q[i].push(ne[i]);
100    			  q[j].push(ne[j]);
101    			  q[k].push(ne[k]);
102    			  d[ne[0]][ne[1]][ne[2]]=d[p[0]][p[1]][p[2]]+1;
103    		    }
104    		}
105    	  }
106        }
107    }
108    int main()
109    {
110        f[0][1]=2;
111        f[0][2]=1;
112        f[1][2]=0;
113        f[1][0]=2;
114        f[2][0]=1;
115        f[2][1]=0;
116        while (scanf("%d %d %d",&s,&m,&n)!=EOF)
117        {
118    	  ans = -1;
119    	  if (s==0&&n==0&&m==0) break;
120    	  if (s%2==1)
121    	  {
122    		cout<<"NO"<<endl;
123    		continue;
124    	  }
125    	  lim[0] = s;
126    	  lim[1] = m;
127    	  lim[2] = n;
128    	  bfs();
129    	  if (ans==-1)
130    	  {
131    		cout<<"NO"<<endl;
132    	  }
133    	  else
134    	  {
135    		cout<<ans<<endl;
136    	  }
137        }
138      
139    	return 0;
140    }
141