hdu1495-非常可乐-（倒水问题bfs）

http://acm.hdu.edu.cn/showproblem.php?pid=1495

题解：

1.最少次数？
江湖套路，bfs。
2.怎么倒？
从一个杯子倒到另一个杯子。
3.倒多少？
因为没有刻度，所以是将自己的水倒完 或者 将别人的未填满部分 填充完。
4.为什么可以这样倒？
因为起始水量和杯子容量都知道，倒水后两边的水量都是已知的，倒水量也是已知的。

#include<stdio.h>

#include<iostream>

#include<algorithm>

#include<cstring>

#include<math.h>

#include<string>

#include<queue>

#include<vector>

#define ll long long

#define inf 0x3f3f3f3f

using namespace std;

struct node

{

    int x,y,z,t;

};

int x,y,z;///杯子容量

bool vis[][][];

int b[];

queue<node>que;

int bfs()

{

    while(!que.empty())

        que.pop();

    memset(vis,false,sizeof(vis));

    que.push({x,,,});

    vis[x][][]=true;

    while(!que.empty())

    {

        node now=que.front();

        que.pop();

        if((now.x==now.y&&now.z==) || (now.x==now.z&&now.y==) || (now.x==&&now.y==now.z) )

        {

            return now.t;

        }

        int a[]={,,,,};

        a[]=now.x;

        a[]=now.y;

        a[]=now.z;///三个杯子

        a[]=now.t;

        int temp[]={,,,,};///临时存储的新的状态

        for(int i=;i<=;i++)///倒水的杯子i

        {

            for(int j=;j<=;j++)///进水的杯子j

            {

                int temp[]={,,,,};

                temp[]=now.x;temp[]=now.y;temp[]=now.z;///和a一样获取now的值，因为只对两个杯子变动，还有一个没变

                int need=b[j]-a[j] ;///被倒进的杯子还需要多少装满

                if( i!=j )///不是同一个杯子

                {

                    if(a[i]<=need)///如果a能倒完

                    {

                        temp[i]=;

                        temp[j]=temp[j]+a[i];

                    }

                    if(a[i]>need)///a不能倒完，就倒need量的水

                    {

                        temp[i]=a[i]-need;

                        temp[j]=a[j]+need;

                    }

                    if( !vis[ temp[] ][ temp[] ][ temp[] ] )

                    {

                        que.push( { temp[],temp[],temp[],a[]+ } );

                        vis[ temp[] ][ temp[] ][ temp[] ]=true;

                    }

                }

            }

        }

    }

    return ;

}

int main()

{

    while(scanf("%d%d%d",&x,&y,&z)&&(x+y+z))

    {

        b[]=x;

        b[]=y;

        b[]=z;///b数组是容量

        int ans=bfs();

        if(ans)

            printf("%d\n",ans);

        else

            printf("NO\n");

    }

    return ;

}