非常可乐
大家一定觉的运动以后喝可乐是一件很惬意的事情，但是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
解题思路：
本题给出多组数据，每组数据包括3个整数可乐体积s，第一个杯子容量n， 另一个杯子容量m。s == n + m 要求输出想要平分可乐最少倒的次数。
这里本题使用BFS，广搜的基本思路是，用一个队列，搜索下一步可以抵达的所有状态加入队列，直到符合条件或队列为空为止。
记录初始状态为可乐瓶中可乐体积为s， 两个杯中的可乐体积都为0， 当前状态若想抵达下一个状态有s向n倒水、s向m倒水、n向s倒水、n向m倒水、m向s倒水、m向n倒水这6种方法，执行完这6种方法后得到的6种状态即为当前状态的下一状态。将当前状态出队寻找下一状态，取所有合法状态加入队列，继续向下搜索即可。
结束条件，由于s == n + m所以若想将可乐分为两相等份，最终的情况一定是，可乐瓶与较大的杯中各有一半可乐，较小的杯中没有可乐。这里可以使用一个数组v[3]，v[0] v[1] v[2]分别记录可乐瓶， 较大的杯子，与较小的杯子的容积。用一个结构体node记录每个状态各容器内的可乐体积与当前状态的倒水次数，布尔数组vis记录状态是否出现过。
struct node{ int v[3]; //v[]0 v[1] v[2] 分别为当前状态可乐瓶、大杯、小杯之内的可乐体积 int step; //step记录倒水次数 }Node; bool vis[maxn][maxn][maxn] = {false}; //记录状态是否出现过
倒水，可以写一个判断倒水函数，传入对应容器x与y，执行x向y倒水，如果被倒入容器y的容积小于两个容器中可乐总体积，就将容器y倒满，如果y的容积大于两容器中的可乐总体积 ，就将所有可乐倒入y容器，两容器中可乐总体积减去y中的可乐体积就是x中剩余的可乐体积。
void judge(int x, int y){ //传入容器x y int sum = Node.v[x] + Node.v[y];//记录两容器中的可乐总体积 if(v[y] <= sum){ //y的容积小于两个容器中可乐总体积 Node.v[y] = v[y]; //将容器y倒满 }else{ //y的容积大于两容器中的可乐总体积 Node.v[y] = sum; //将所有可乐倒入y } Node.v[x] = sum - Node.v[y]; //两容器中可乐总体积减去y中的可乐体积，x中剩余的可乐体积 }
AC代码
#include <bits/stdc++.h> using namespace std; const int maxn = 110; struct node{ int v[3]; //v[]0 v[1] v[2] 分别为当前状态可乐瓶、大杯、小杯之内的可乐体积 int step; //step记录倒水次数 }Node; bool vis[maxn][maxn][maxn] = {false}; //记录状态是否出现过 int v[3]; void judge(int x, int y){ //传入容器x y int sum = Node.v[x] + Node.v[y];//记录两容器中的可乐总体积 if(v[y] <= sum){ //y的容积小于两个容器中可乐总体积 Node.v[y] = v[y]; //将容器y倒满 }else{ //y的容积大于两容器中的可乐总体积 Node.v[y] = sum; //将所有可乐倒入y } Node.v[x] = sum - Node.v[y]; //两容器中可乐总体积减去y中的可乐体积，x中剩余的可乐体积 } void BFS(){ Node.v[0] = v[0]; Node.v[1] = 0; Node.v[2] = 0; Node.step = 0; //记录初始状态，可乐瓶中体积为s，两个杯中的可乐体积都为0 memset(vis, false, sizeof(vis)); //初始化所有状态为未出现过 vis[Node.v[0]][Node.v[1]][Node.v[2]] = true; //标记当前状态为已出现 queue<node> Q; //队列Q记录当前可操作状态 Q.push(Node); //当前状态入队 while(!Q.empty()){ node top = Q.front(); //取出队首元素 if(top.v[0] == top.v[1] && top.v[2] == 0){ //可乐瓶与较大的杯中各有一半可乐，较小的杯中没有可乐 printf("%d ", top.step);//输出次数 return; } Q.pop(); for(int i = 0; i < 3; i++){ //搜索所有6种状态 for(int j = 0; j < 3; j++){ if(i != j){ //自己不能向自己倒水 Node = top; judge(i , j); //执行i向j倒水 if(!vis[Node.v[0]][Node.v[1]][Node.v[2]]){ //若新状态之前没有出现过 Node.step++; //倒水次数加一 vis[Node.v[0]][Node.v[1]][Node.v[2]] = true; //标记新状态为已出现 Q.push(Node); //新状态入队 } } } } } printf("NO "); //若不能分成两份输出NO } int main() { int s, n, m; while(scanf("%d%d%d", &s, &n, &m) != EOF && s || n || m){ //输入s n m 以0为结束标志 v[0] = s; //获得大杯与小杯的容积 if(n > m){ v[1] = n; v[2] = m; }else{ v[1] = m; v[2] = n; } BFS(); } return 0; }