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[105][105][105];
int b[5];
queue<node>que;

int bfs()
{
    while(!que.empty())
        que.pop();
    memset(vis,false,sizeof(vis));
    que.push({x,0,0,0});
    vis[x][0][0]=true;
    while(!que.empty())
    {
        node now=que.front();
        que.pop();
        if((now.x==now.y&&now.z==0) || (now.x==now.z&&now.y==0) || (now.x==0&&now.y==now.z) )
        {
            return now.t;
        }
        int a[5]={0,0,0,0,0};
        a[1]=now.x;
        a[2]=now.y;
        a[3]=now.z;///三个杯子
        a[4]=now.t;

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

        for(int i=1;i<=3;i++)///倒水的杯子i
        {
            for(int j=1;j<=3;j++)///进水的杯子j
            {
                int temp[5]={0,0,0,0,0};
                temp[1]=now.x;temp[2]=now.y;temp[3]=now.z;///和a一样获取now的值，因为只对两个杯子变动，还有一个没变
                int need=b[j]-a[j] ;///被倒进的杯子还需要多少装满
                if( i!=j )///不是同一个杯子
                {
                    if(a[i]<=need)///如果a能倒完
                    {
                        temp[i]=0;
                        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[1] ][ temp[2] ][ temp[3] ] )
                    {
                        que.push( { temp[1],temp[2],temp[3],a[4]+1 } );
                        vis[ temp[1] ][ temp[2] ][ temp[3] ]=true;
                    }
                }
            }
        }
    }
    return 0;
}


int main()
{

    while(scanf("%d%d%d",&x,&y,&z)&&(x+y+z))
    {
        b[1]=x;
        b[2]=y;
        b[3]=z;///b数组是容量
        int ans=bfs();
        if(ans)
            printf("%d
",ans);
        else
            printf("NO
");
    }
    return 0;
}