- 题目描述：
大家一定觉的运动以后喝可乐是一件很惬意的事情，但是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 3
4 1 3
0 0 0
- 样例输出：
NO
3
这个题一开始也是没什么思路。这些瓶子倒来倒去真实麻烦。后来反应过来应该用深搜或广搜来解决此类问题。深搜的代码写了一半，突然发觉还是用广搜更好些
代码如下#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std; int v[][][]; int ans = -;
int s, n, m;
struct State
{
int a, b, c;
State(int a, int b, int c) {
this->a = a, this->b = b, this->c = c;
}
};
queue <State>que; int main(int argc, char const *argv[])
{ while (scanf("%d %d %d", &s, &n, &m) != EOF && (s != && n != && m != )) {
if (s & ) {
puts("NO");
}
else {
int ans = -;
memset(v, -, sizeof(v));
while (!que.empty()) {
que.pop();
}
que.push(State(s, , ));
v[s][][] = ;
while (!que.empty()) {
State p = que.front(); que.pop();
if ((p.a == p.b && p.a == s/) || (p.a == p.c && p.a == s/) || (p.b == p.c && p.b == s/)) {
ans = v[p.a][p.b][p.c];
break;
}
else {
int ra = s - p.a;
int rb = n - p.b;
int rc = m - p.c;
int step = v[p.a][p.b][p.c] + ;
if (ra > ) {
int tmp = min(ra, p.b);
int at = p.a + tmp;
int bt = p.b - tmp;
int ct = p.c;
if (v[at][bt][ct] == - || step < v[at][bt][ct]) {
if (tmp != ) {
que.push(State(at, bt, ct));
v[at][bt][ct] = step;
}
} tmp = min(ra, p.c);
at = p.a + tmp;
bt = p.b;
ct = p.c - tmp;
if (v[at][bt][ct] == - || step < v[at][bt][ct]) {
if (tmp != ) {
que.push(State(at, bt, ct));
v[at][bt][ct] = step;
}
} }
if (rb > ) {
int tmp = min(rb, p.a);
int at = p.a - tmp;
int bt = p.b + tmp;
int ct = p.c;
if (v[at][bt][ct] == - || step < v[at][bt][ct]) {
if (tmp != ) {
que.push(State(at, bt, ct));
v[at][bt][ct] = step;
}
} tmp = min(rb, p.c);
at = p.a;
bt = p.b + tmp;
ct = p.c - tmp;
if (v[at][bt][ct] == - || step < v[at][bt][ct]) {
if (tmp != ) {
que.push(State(at, bt, ct));
v[at][bt][ct] = step;
}
}
}
if (rc > ) {
int tmp = min(rc, p.a);
int at = p.a - tmp;
int bt = p.b ;
int ct = p.c + tmp;
if (v[at][bt][ct] == - || step < v[at][bt][ct]) {
if (tmp != ) {
que.push(State(at, bt, ct));
v[at][bt][ct] = step;
}
} tmp = min(rc, p.b);
at = p.a;
bt = p.b - tmp;
ct = p.c + tmp;
if (v[at][bt][ct] == - || step < v[at][bt][ct]) {
if (tmp != ) {
que.push(State(at, bt, ct));
v[at][bt][ct] = step;
}
}
}//if(rc)
}//else
}//while(queue)
if (ans == -) {
puts("NO");
}
else {
printf("%d\n", ans);
} }//else s is even
}//while(scanf)
return ;
}