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