非常可樂

Time Limit: 2000/1000 MS (java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 12643    Accepted Submission(s): 5066

PRoblem Description

大家一定覺的運動以后喝可樂是一件很愜意的事情，但是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

題解:觀察這道題目，發現它的初始狀態就是m=0,n=0,s=s.(n是大杯里的量，m是小杯里的量，s是可樂瓶里的量)，如果想要它們平分，最后一定是n=s/2,s=s/2,m=0。就是說大杯子和可樂瓶里的量各是總量的一半就表示能平分。我們只要朝著這個方向靠攏就可以了，而又要求最小的步數，有一個初始的狀態又有終點狀態，還要求最小步數，可以想到用bfs求解。乍一看還真跟bfs扯不上關系，仔細分析它每一步就6個方向（s->n,s->m,m->n,n->m,n->s,m->s），相當于bfs迷宮求解中的方向。

對這6個方向用bfs最后在n=s/2,s=s/2的時候結束，就可以完成了。這題只要想清楚這些，具體這個水怎么倒的就交給電腦去完成吧，我們只要坐等答案就好了。

另外當可樂總容量為奇數的時候怎么倒都不可能平分所以直接排除就行了。

AC代碼:

#include<iostream>

#include<queue>

#include<string.h>

using namespace std;

const int N=105;

struct node

{

    int n,m,s,t;

}now;

bool vis[N][N];

int n,m,s;

int bfs()

{

    now.n=0,now.m=0,now.s=s,now.t=0;

    memset(vis,0,sizeof(vis));

    queue<node>q;

    vis[n][m]=1;

    q.push(now);

    while(!q.empty())

    {

        node cur=q.front(),v;

        q.pop();

        if(cur.s==s/2&&cur.n==s/2)

            return cur.t;

        if(cur.s&&cur.n!=n)//s->n

        {

            int c=n-cur.n;

            if(cur.s>=c)

            {

                v.n=n;

                v.s=cur.s-c;

            }

            else

            {

                v.s=0;

                v.n=cur.n+cur.s;

            }

            v.m=cur.m;

            v.t=cur.t+1;

            if(!vis[v.n][v.m])

            {

                q.push(v);

                vis[v.n][v.m]=1;

            }

        }

        if(cur.s&&cur.m!=m)//s->m

        {

            int c=m-cur.m;

            if(cur.s>=c)

            {

                v.m=m;

                v.s=cur.s-c;

            }

            else

            {

                v.s=0;

                v.m=cur.m+cur.s;

            }

            v.n=cur.n;

            v.t=cur.t+1;

            if(!vis[v.n][v.m])

            {

                q.push(v);

                vis[v.n][v.m]=1;

            }

        }

        if(cur.n&&cur.s!=s)//n->s

        {

            int c=s-cur.s;

            if(cur.n>=c)

            {

                v.s=s;

                v.n=cur.n-c;

            }

            else

            {

                v.n=0;

                v.s=cur.s+cur.n;

            }

            v.m=cur.m;

            v.t=cur.t+1;

            if(!vis[v.n][v.m])

            {

                q.push(v);

                vis[v.n][v.m]=1;

            }

        }

        if(cur.m&&cur.s!=s)//m->s

        {

            int c=s-cur.s;

            if(cur.m>=c)

            {

                v.s=s;

                v.m=cur.m-c;

            }

            else

            {

                v.m=0;

                v.s=cur.s+cur.m;

            }

            v.n=cur.n;

            v.t=cur.t+1;

            if(!vis[v.n][v.m])

            {

                q.push(v);

                vis[v.n][v.m]=1;

            }

        }

        if(cur.n&&cur.m!=m)//n->m

        {

            int c=m-cur.m;

            if(cur.n>=c)

            {

                v.m=m;

                v.n=cur.n-c;

            }

            else

            {

                v.n=0;

                v.m=cur.m+cur.n;

            }

            v.s=cur.s;

            v.t=cur.t+1;

            if(!vis[v.n][v.m])

            {

                q.push(v);

                vis[v.n][v.m]=1;

            }

        }

        if(cur.m&&cur.n!=n)//m->n

        {

            int c=n-cur.n;

            if(cur.m>=c)

            {

                v.n=n;

                v.m=cur.m-c;

            }

            else

            {

                v.m=0;

                v.n=cur.n+cur.m;

            }

            v.s=cur.s;

            v.t=cur.t+1;

            if(!vis[v.n][v.m])

            {

                q.push(v);

                vis[v.n][v.m]=1;

            }

        }

    }

    return 0;

}

int main()

{

    while(cin>>s>>n>>m)

    {

        int t;

        if(s==0&&n==0&&m==0)

            break;

        if(s%2!=0)

        {

            cout<<"NO"<<endl;

            continue;

        }

        if(n<m)

            {

                t=n;

                n=m;

                m=t;

            }

        int ans=bfs();

        if(ans)

            cout<<ans<<endl;

        else

            cout<<"NO"<<endl;

    }

    return 0;

}