K - 非常可樂 （bfs）

K - 非常可樂

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

此題：需要三個杯子中任意兩個要平分所有飲料

//Full of love and hope for life


#include <iostream>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <stdio.h>
#include <queue>
using namespace std;

struct node
{
    int x,y,z,step;//記錄三個杯子的飲料量
};

node n,m;
int a,b,c;
int flag[110][110][110];//判斷是否已經有過的情況

void bfs(int a,int b,int c)
{
    queue<node>q;
    n.x=0;
    n.y=0;
    n.z=c*2;//這裡的c是所有飲料的一半
    n.step=0;
    q.push(n);
    flag[n.x][n.y][n.z]=1;
    while(!q.empty())
    {
        m=q.front();
        q.pop();
        if((m.x==m.y&&m.x+m.y==2*c)||(m.x==m.z&&m.x+m.z==2*c)||(m.z==m.y&&m.z+m.y==2*c))//必須這樣
        {
            cout << m.step << endl;
            return ;
        }
        for(int i=0; i<6; i++)
        {
            if(i==0)//a倒b
            {
                n.x=a;
                n.y=m.y;
                n.z=m.z+m.x-a;
                if(n.z<0)
                {
                    n.x=n.z+a;
                    n.z=0;
                }
            }
            if(i==1)//a倒c
            {
                n.x=m.x;
                n.y=b;
                n.z=m.z+m.y-b;
                if(n.z<0)
                {
                    n.y=n.z+b;
                    n.z=0;
                }
            }
            if(i==2)//b倒a
            {
                n.x=0;
                n.y=m.y;
                n.z=m.z+m.x;
            }
            if(i==3)//c倒a
            {
                n.x=m.x;
                n.y=0;
                n.z=m.z+m.y;
            }
            if(i==4)//b倒c
            {
                n.z=m.z;
                n.y=m.x+m.y;
                if(n.y>=b)
                {
                    n.x=n.y-b;
                    n.y=b;
                }
                else
                {
                    n.x=0;
                }
            }
            if(i==5)//c倒b
            {
                n.z=m.z;
                n.x=m.x+m.y;
                if(n.x>=a)
                {
                    n.y=n.x-a;
                    n.x=a;
                }
                else
                {
                    n.y=0;
                }
            }
            if(flag[n.x][n.y][n.z]==0)
            {
                n.step=m.step+1;
                q.push(n);
                flag[n.x][n.y][n.z]=1;
            }
        }
    }
    cout << "NO" << endl;
    return ;
}

int main()
{
    while(cin >> a >> b >> c)
    {
        if(a==0&&b==0&&c==0)
        {
            break;
        }
        if(a%2==0)
        {
            memset(flag,0,sizeof(flag));
            a=a/2;
            bfs(b,c,a);
        }
        else
        {
            cout << "NO" << endl;
        }
    }
    return 0;
}