HDU -1495 非常可乐 BFS

题意:（中文的就不多说了）
思路:每一次倒水有六种方法,即（s->a ; s->b ; a->s ; a->b ; b->s ; b->a）,我们要得到最少的倒的次数，当然就是bfs咯。
（不过好像也可以用数论方面的知识做,听说很简单哦,可惜我数学太弱了,只能用最笨的bfs咯）
具体请看代码:

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<set>
#include<queue>
#include<stack>
#include<cstdlib>
#define CLR(x) memset(x,0,sizeof(x))
#define ll long long int
#define db double
using namespace std;
const int maxn=105;
int vis[maxn][maxn][maxn];
int s,a,b;
struct node
{
    int a,b,s,t;
};

int bfs()
{
    queue<node>q;
    node a1;
    a1.a=0,a1.b=0,a1.s=s,a1.t=0;//开始都没倒,所以初始化为0.
    q.push(a1);
    memset(vis,0,sizeof(vis));
    vis[a1.a][a1.b][a1.s]=1;//标记这种状态.
    while(!q.empty())
    {
        node u,v;
        u=q.front();
        //能平分的条件是可乐瓶和容量大(a)的杯子都装着最开始一半的可乐
        //看懂题意啊,中途是不能喝的,必须倒匀了才行.所以要处理成a为两个杯子中的大号.
        if(u.a==s/2 && u.s==s/2)//是总容量的一半.
            return u.t;
        if(u.s && u.a!=a)  //s->a
        {
            int m=a-u.a;
            if(u.s>=m) v.a=a,v.s=u.s-m;  //可以倒就倒满.
            else v.a=u.a+u.s,v.s=0;
            v.b=u.b;
            if(!vis[v.a][v.b][v.s]){
                vis[v.a][v.b][v.s]=1;
                v.t=u.t+1;
                q.push(v);
            }
        }
        if(u.s && u.b!=b) //s->b
        {
            int m=b-u.b;
            if(u.s>=m) v.b=b,v.s=u.s-m;
            else v.b=u.b+u.s,v.s=0;
            v.a=u.a;
            if(!vis[v.a][v.b][v.s]){
                vis[v.a][v.b][v.s]=1;
                v.t=u.t+1;
                q.push(v);
            }
        }
        if(u.a && u.b!=b) //a->b
        {
            int m=b-u.b;
            if(u.a>=m) v.b=b,v.a=u.a-m;
            else v.b=u.b+u.a,v.a=0;
            v.s=u.s;
            if(!vis[v.a][v.b][v.s]){
                vis[v.a][v.b][v.s]=1;
                v.t=u.t+1;
                q.push(v);
            }
        }
        if(u.a && u.s!=s) //a->s
        {
            int m=s-u.s;
            if(u.a>=m) v.s=s,v.a=u.a-m;
            else v.s=u.s+u.a,v.a=0;
            v.b=u.b;
            if(!vis[v.a][v.b][v.s]){
                vis[v.a][v.b][v.s]=1;
                v.t=u.t+1;
                q.push(v);
            }
        }
        if(u.b && u.a!=a) //b->a
        {
            int m=a-u.a;
            if(u.b>=m) v.a=a,v.b=u.b-m;
            else v.a=u.a+u.b,v.b=0;
            v.s=u.s;
            if(!vis[v.a][v.b][v.s]){
                vis[v.a][v.b][v.s]=1;
                v.t=u.t+1;
                q.push(v);
            }
        }
        if(u.b && u.s!=s) //b->s
        {
            int m=s-u.s;
            if(u.b>=m) v.s=s,v.b=u.b-m;
            else v.s=u.s+u.b,v.b=0;
            v.a=u.a;
            if(!vis[v.a][v.b][v.s]){
                vis[v.a][v.b][v.s]=1;
                v.t=u.t+1;
                q.push(v);
            }
        }
        q.pop();
    }
    return 0;
}
int main()
{
    while(scanf("%d %d %d",&s,&a,&b)!=EOF )
    {
        if(s+a+b==0)
            break;
        if(a<b) swap(a,b);//即直接看大号的杯子能否装下一半,方便BFS结束时的判定.
        if(s%2)
            puts("NO");
        else{
            int ans=bfs();
            if(!ans)  puts("NO");
            else printf("%d\n",ans);
        }
    }
}