题目：http://acm.hdu.edu.cn/showproblem.php?pid=1495
Problem Description
大家一定觉的运动以后喝可乐是一件很惬意的事情，但是seeyou却不这么认为。因为每次当seeyou买了可乐以后，阿牛就要求和seeyou一起分享这一瓶可乐，而且一定要喝的和seeyou一样多。但seeyou的手中只有两个杯子，它们的容量分别是N 毫升和M 毫升 可乐的体积为S （S<101）毫升 (正好装满一瓶) ，它们三个之间可以相互倒可乐 (都是没有刻度的，且 S==N+M，101＞S＞0，N＞0，M＞0) 。聪明的ACMER你们说他们能平分吗？如果能请输出倒可乐的最少的次数，如果不能输出"NO"。3
中文题目，不解释。
这是一道BFS，每次倒可乐动作可以看为：
从瓶中向第一个杯子倒，向第二个杯子倒；
从第一个杯子向瓶子倒，向第二个杯子倒；
从第二个杯子向瓶子倒，向第一个杯子倒。
这六种情况，O(∩_∩)O~~
搜索方向确定了吧？
我的方法是每次要倒得时候判断，该容器可不可以倒可乐（该容器满没满）
然后是细节处理：
例如如果从第一个杯子向第二个杯子倒。
①第二个杯子是否可以倒可乐（是否满了）
②第一个杯子是否是空的
③第一个杯子向第二个杯子倒完后，会不会溢出。
④第一个杯子如果剩余，剩余多少（由第一个杯子原来是否有可乐决定）
遍历数组，VIS此处可以建立三维数组，让各个容器内可乐容量作为三个下标。
OK~如此以来，向着AC进发吧~！
#include <iostream>
#include <string.h>
#include <queue>
using namespace std;
int s,n,m;
bool vis[101][101][101];
struct Cola
{
int v,v1,v2;
int sp;
};
bool judge(Cola c)
{
if(!c.sp) return 0;
if( (c.v==c.v1&&!c.v2) || (c.v==c.v2&&!c.v1) || (c.v1==c.v2 && !c.v) ) return 1;
return 0;
}
int bfs(int v,int v1,int v2)
{
memset(vis,0,sizeof(vis));
queue <Cola> q;
Cola pre,lst;
pre.v=v;
pre.v1=v1;
pre.v2=v2;
pre.sp=0;
vis[pre.v][pre.v1][pre.v2]=1;
q.push(pre);
while(!q.empty())
{
pre=q.front();
q.pop();
if(judge(pre)) return pre.sp;
// 瓶子没装满，可以向瓶子倒可乐
if(pre.v!=s)
{
// v1内有可乐
if(pre.v1)
{
lst.v=pre.v+pre.v1;
lst.v1=0;
lst.v2=pre.v2;
if(!vis[lst.v][lst.v1][lst.v2])
{
vis[lst.v][lst.v1][lst.v2]=1;
lst.sp=pre.sp+1;
q.push(lst);
}
}
// v2内有可乐
if(pre.v2)
{
lst.v=pre.v+pre.v2;
lst.v2=0;
lst.v1=pre.v1;
if(!vis[lst.v][lst.v1][lst.v2])
{
vis[lst.v][lst.v1][lst.v2]=1;
lst.sp=pre.sp+1;
q.push(lst);
}
}
}
// 如果v1杯子没有满
if(pre.v1!=n)
{
if(pre.v)
{
lst.v1=n;
// 还有可能原来杯子中有一些可乐，并非是空的
lst.v=(pre.v-n+pre.v1);
lst.v2=pre.v2;
if(!vis[lst.v][lst.v1][lst.v2])
{
vis[lst.v][lst.v1][lst.v2]=1;
lst.sp=pre.sp+1;
q.push(lst);
}
}
if(pre.v2)
{
lst.v=pre.v;
// 如果v2向v1倒可乐时，v1可乐会溢出（导致v2有剩余）
if(pre.v2+pre.v1>n)
{
lst.v1=n;
lst.v2=pre.v2+pre.v1-n;
}
else
{
lst.v1=pre.v1+pre.v2;
lst.v2=0;
}
if(!vis[lst.v][lst.v1][lst.v2])
{
vis[lst.v][lst.v1][lst.v2]=1;
lst.sp=pre.sp+1;
q.push(lst);
}
}
}
// 如果v2没有满
if(pre.v2!=m)
{
if(pre.v)
{
lst.v2=m;
// 还有可能原来杯子中有一些可乐，并非是空的
lst.v=(pre.v-m+pre.v2);
lst.v1=pre.v1;
if(!vis[lst.v][lst.v1][lst.v2])
{
vis[lst.v][lst.v1][lst.v2]=1;
lst.sp=pre.sp+1;
q.push(lst);
}
}
if(pre.v1)
{
lst.v=pre.v;
// 如果v1向v2倒可乐时，v2可乐会溢出（导致v1有剩余）
if(pre.v2+pre.v1>m)
{
lst.v2=m;
lst.v1=pre.v2+pre.v1-m;
}
else
{
lst.v2=pre.v1+pre.v2;
lst.v1=0;
}
if(!vis[lst.v][lst.v1][lst.v2])
{
vis[lst.v][lst.v1][lst.v2]=1;
lst.sp=pre.sp+1;
q.push(lst);
}
}
}
}
return -1;
}
int main()
{
int step;
while(cin>>s>>n>>m)
{
if(!s && !n && !m) break;
// 可乐总体积为奇数，怎么倒也不能平分
if(s%2) {cout<<"NO"<<endl;continue;}
step=bfs(s,0,0);
if(step==-1) cout<<"NO"<<endl;
else cout<<step<<endl;
}
return 0;
}
ACM-BFS之非常可乐——hdu1495,布布扣,bubuko.com
原文：http://blog.csdn.net/lttree/article/details/24129507