非常可樂

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

PRoblem Description

大家一定覺的運(yùn)動以后喝可樂是一件很愜意的事情，但是seeyou卻不這么認(rèn)為。因?yàn)槊看萎?dāng)seeyou買了可樂以后，阿牛就要求和seeyou一起分享這一瓶可樂，而且一定要喝的和seeyou一樣多。但seeyou的手中只有兩個(gè)杯子，它們的容量分別是N毫升和M毫升 可樂的體積為S（S<101）毫升　(正好裝滿一瓶)，它們?nèi)齻€(gè)之間可以相互倒可樂 (都是沒有刻度的，且S==N+M，101＞S＞0，N＞0，M＞0)。聰明的ACMER你們說他們能平分嗎？如果能請輸出倒可樂的最少的次數(shù)，如果不能輸出"NO"。

Input

三個(gè)整數(shù) : S 可樂的體積, N 和M是兩個(gè)杯子的容量，以"0 0 0"結(jié)束。

Output

如果能平分的話請輸出最少要倒的次數(shù)，否則輸出"NO"。

Sample Input

7 4 3

4 1 3

0 0 0

Sample Output

NO

3

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

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

另外當(dāng)可樂總?cè)萘繛槠鏀?shù)的時(shí)候怎么倒都不可能平分所以直接排除就行了。

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;

}