题目描述：

大家一定觉的运动以后喝可乐是一件很惬意的事情，但是seeyou却不这么认为。因为每次当seeyou买了可乐以后，阿牛就要求和seeyou一起分享这一瓶可乐，而且一定要喝的和seeyou一样多。但seeyou的手中只有两个杯子，它们的容量分别是N 毫升和M 毫升 可乐的体积为S （S<101）毫升(正好装满一瓶) ，它们三个之间可以相互倒可乐 (都是没有刻度的，且 S==N+M，101＞S＞0，N＞0，M＞0) 。聪明的ACMER你们说他们能平分吗？如果能请输出倒可乐的最少的次数，如果不能输出"NO"。

输入：

三个整数 : S 可乐的体积 , N 和 M是两个杯子的容量，以"0 0 0"结束。

输出：

如果能平分的话请输出最少要倒的次数，否则输出"NO"。

样例输入：

7 4 34 1 30 0 0

样例输出：

NO3
这个题一开始也是没什么思路。这些瓶子倒来倒去真实麻烦。后来反应过来应该用深搜或广搜来解决此类问题。深搜的代码写了一半，突然发觉还是用广搜更好些
代码如下

  1 #include <cstdio>  2 #include <iostream>  3 #include <cstring>  4 #include <queue>  5 #include <algorithm>  6 using namespace std;  7   8 int v[110][110][110];  9  10 int ans = -1; 11 int s, n, m; 12 struct State 13 { 14     int a, b, c; 15     State(int a, int b, int c) { 16         this->a = a, this->b = b, this->c = c; 17     } 18 }; 19 queue <State>que; 20  21 int main(int argc, char const *argv[]) 22 { 23  24     while (scanf("%d %d %d", &s, &n, &m) != EOF && (s != 0 && n != 0 && m != 0)) { 25         if (s & 1) { 26             puts("NO"); 27         } 28         else { 29             int ans = -1; 30             memset(v, -1, sizeof(v)); 31             while (!que.empty()) { 32                 que.pop(); 33             } 34             que.push(State(s, 0, 0)); 35             v[s][0][0] = 0; 36             while (!que.empty()) { 37                 State p = que.front(); que.pop(); 38                 if ((p.a == p.b && p.a == s/2) || (p.a == p.c && p.a == s/2) || (p.b == p.c && p.b == s/2)) { 39                     ans = v[p.a][p.b][p.c]; 40                     break; 41                 } 42                 else { 43                     int ra = s - p.a; 44                     int rb = n - p.b; 45                     int rc = m - p.c; 46                     int step = v[p.a][p.b][p.c] + 1; 47                     if (ra > 0) { 48                         int tmp = min(ra, p.b); 49                         int at = p.a + tmp; 50                         int bt = p.b - tmp; 51                         int ct = p.c; 52                         if (v[at][bt][ct] == -1 || step < v[at][bt][ct]) { 53                             if (tmp != 0) { 54                                 que.push(State(at, bt, ct)); 55                                 v[at][bt][ct] = step; 56                             } 57                         } 58  59                         tmp = min(ra, p.c); 60                         at = p.a + tmp; 61                         bt = p.b; 62                         ct = p.c - tmp; 63                         if (v[at][bt][ct] == -1 || step < v[at][bt][ct]) { 64                             if (tmp != 0) { 65                                 que.push(State(at, bt, ct)); 66                                 v[at][bt][ct] = step; 67                             } 68                         } 69                          70                     } 71                     if (rb > 0) { 72                         int tmp = min(rb, p.a); 73                         int at = p.a - tmp; 74                         int bt = p.b + tmp; 75                         int ct = p.c; 76                         if (v[at][bt][ct] == -1 || step < v[at][bt][ct]) { 77                             if (tmp != 0) { 78                                 que.push(State(at, bt, ct)); 79                                 v[at][bt][ct] = step; 80                             } 81                         } 82  83                         tmp = min(rb, p.c); 84                         at = p.a; 85                         bt = p.b + tmp; 86                         ct = p.c - tmp; 87                         if (v[at][bt][ct] == -1 || step < v[at][bt][ct]) { 88                             if (tmp != 0) { 89                                 que.push(State(at, bt, ct)); 90                                 v[at][bt][ct] = step; 91                             } 92                         } 93                     } 94                     if (rc > 0) { 95                         int tmp = min(rc, p.a); 96                         int at = p.a - tmp; 97                         int bt = p.b ; 98                         int ct = p.c + tmp; 99                         if (v[at][bt][ct] == -1 || step < v[at][bt][ct]) {100                             if (tmp != 0) {101                                 que.push(State(at, bt, ct));102                                 v[at][bt][ct] = step;103                             }104                         }105 106                         tmp = min(rc, p.b);107                         at = p.a;108                         bt = p.b - tmp;109                         ct = p.c + tmp;110                         if (v[at][bt][ct] == -1 || step < v[at][bt][ct]) {111                             if (tmp != 0) {112                                 que.push(State(at, bt, ct));113                                 v[at][bt][ct] = step;114                             }115                         }116                     }//if(rc)117                 }//else118             }//while(queue)119             if (ans == -1) {120                 puts("NO");121             }122             else {123                 printf("%d\n", ans);124             }125             126         }//else s is even127     }//while(scanf)128     return 0;129 }

 

九度oj 题目1457：非常可乐