hdu 1495（bfs）

bfs分六种情况往下走，模拟倒的过程。

注意退出时必须是两个杯子均为s / 2，而不能是一个杯子，有可能另一半没汇聚到一个杯子里呢。WA了好几次...

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn = 110;
int s, n, m;
struct Node
{
    int a, b, ss;
    int step;
    Node()  {}
    Node(int x, int y, int z, int dep)
    {
        a = x;  b = y;  ss = z; step = dep;
    }
};
bool vis[maxn][maxn][maxn];


int bfs()
{
    queue<Node> q;
    q.push(Node(0, 0, s, 0));
    vis[0][0][s] = 1;

    while(!q.empty())
    {
        Node head = q.front();
        q.pop();

        int cura = head.a, curb = head.b, curs = head.ss;
        int step = head.step;
        //cout << cura << " " << curb << " " << curs << endl;

        if((cura == s / 2 && curb == s / 2) || (cura == s / 2 && curs == s / 2) || (curb == s / 2 && curs == s / 2))
        {
            return step;
        }

        int newa, newb, news;

        if(curs && cura != n)
        {
            if(curs + cura >= n)        //s - > a
            {
                newa = n;   news = curs + cura - n;    newb = curb;
            }
            else
            {
                newa = curs + cura;   news = 0;    newb = curb;
            }
            if(!vis[newa][newb][news])
            {
                q.push(Node(newa, newb, news, step + 1));
                vis[newa][newb][news] = 1;
            }
        }

        if(curs && curb != m)
        {
            if(curs + curb >= m)                //s - > b
            {
                newa = cura;   news = curs + curb - m;    newb = m;
            }
            else
            {
                newa = cura;   news = 0;    newb = curs + curb;
            }
            if(!vis[newa][newb][news])
            {
                q.push(Node(newa, newb, news, step + 1));
                vis[newa][newb][news] = 1;
            }
        }


        if(cura && curs != s)
        {
               
            if(cura + curs >= s)        //a - > s
            {
                newa = cura + curs - s;   news = s;    newb = curb;
            }
            else
            {
                newa = 0;   news = cura + curs;    newb = curb;
            }
            if(!vis[newa][newb][news])
            {
                q.push(Node(newa, newb, news, step + 1));
                vis[newa][newb][news] = 1;
            }
        }

        if(cura && curb != m)
        {
            if(cura + curb >= m)                                //a - > b
            {
                newa = cura + curb - m; newb = m;   news = curs;
            }
            else
            {
                newa = 0;   newb = cura + curb; news = curs;
            }
            if(!vis[newa][newb][news])
            {
                q.push(Node(newa, newb, news, step + 1));
                vis[newa][newb][news] = 1;
            }
        }


        if(curb && curs != s)
        {
                    
            if(curb + curs >= s)        //b - > s
            {
                newa = cura;   news = s;    newb = curb + curs - s;
            }
            else
            {
                newa = cura;   news = curb + curs;    newb = 0;
            }
            if(!vis[newa][newb][news])
            {
                q.push(Node(newa, newb, news, step + 1));
                vis[newa][newb][news] = 1;
            }
        }

        if(curb && cura != n)
        {
            if(cura + curb >= n)                                //b - > a
            {
                newa = n; newb = cura + curb - n;   news = curs;
            }
            else
            {
                newa = cura + curb;   newb = 0; news = curs;
            }
            if(!vis[newa][newb][news])
            {
                q.push(Node(newa, newb, news, step + 1));
                vis[newa][newb][news] = 1;
            }
        }
    }
    return 0;
}


int main()
{
    while(scanf("%d%d%d", &s, &n, &m) == 3 && (s && n && m))
    {
        memset(vis, 0, sizeof(vis));
        if(s & 1)
        {
            printf("NO\n"); continue;
        }
        int ans = bfs();
        if(ans) printf("%d\n", ans);
        else    printf("NO\n");
    }
    return 0;
}