首页 > 代码库 > hdu1495(bfs)

hdu1495(bfs)

 

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1495

题意:有三个杯子,开始时第一个杯子装满水(体积为a),倒来倒去,得到其中2个杯里的水的体积都为a/2,求最小次数,不存在就输出NO。

分析:因为被子没有刻度,所以倒入时要倒满或倒完才能保证知道容积,即有6种情况来分别遍历。

#include <iostream>#include <cstdlib>#include <queue>#include <vector>#include <cstdio>#include <map>#include <cstring>#include <algorithm>#define INF 100000000#define maxn 111111#define ll __int64#define lson 1,m,rt<<1#define rson m+1,r,rt<<1|1using namespace std;int vis[110][110][110];int a,b,c,flag;struct node{    int x,y,z;    int step;};int judge(node k){    if((k.x==k.y&&k.z==0)||(k.x==k.z&&k.y==0)||(k.y==k.z&&k.x==0))        return 1;    return 0;}void bfs(){    queue<node>que;    node now,next;    int num;    now.x=a;now.y=0;    now.z=0;now.step=0;    vis[a][0][0]=1;    que.push(now);    while(!que.empty())    {        now=que.front();que.pop();        if(judge(now))        {            printf("%d\n",now.step);            flag=1;            return;        }        if(now.x>0)//a倒入其他        {            if(b>now.y)//a倒入b            {                num=b-now.y;                next.z=now.z;                next.step=now.step+1;                if(now.x>num)//a倒不完                {                    next.x=now.x-num;                    next.y=b;                }                else//倒完                {                    next.y=now.x+now.y;                    next.x=0;                }                if(!vis[next.x][next.y][next.z])                {                    vis[next.x][next.y][next.z]=1;                    que.push(next);                }            }            if(c>now.z)//a倒入c            {                num=c-now.z;                next.y=now.y;                next.step=now.step+1;                if(now.x>num)//倒不完                {                    next.x=now.x-num;                    next.z=c;                }                else//倒完                {                    next.z=now.x+now.z;                    next.x=0;                }                if(!vis[next.x][next.y][next.z])                {                    vis[next.x][next.y][next.z]=1;                    que.push(next);                }            }        }        if(now.y>0)//b倒入其他        {            if(a>now.x)            {                num=a-now.x;                next.z=now.z;                next.step=now.step+1;                if(now.y>num)                {                    next.y=now.y-num;                    next.x=a;                }                else                {                    next.x=now.x+now.y;                    next.y=0;                }                if(!vis[next.x][next.y][next.z])                {                    vis[next.x][next.y][next.z]=1;                    que.push(next);                }            }            if(c>now.z)            {                num=c-now.z;                next.x=now.x;                next.step=now.step+1;                if(now.y>num)                {                    next.y=now.y-num;                    next.z=c;                }                else                {                    next.z=now.y+now.z;                    next.y=0;                }                if(!vis[next.x][next.y][next.z])                {                    vis[next.x][next.y][next.z]=1;                    que.push(next);                }            }        }        if(now.z>0)//c倒入其他        {            if(b>now.y)            {                num=b-now.y;                next.x=now.x;                next.step=now.step+1;                if(now.z>num)                {                    next.z=now.z-num;                    next.y=b;                }                else                {                    next.y=now.z+now.y;                    next.z=0;                }                if(!vis[next.x][next.y][next.z])                {                    vis[next.x][next.y][next.z]=1;                    que.push(next);                }            }            if(a>now.x)            {                num=a-now.x;                next.y=now.y;                next.step=now.step+1;                if(now.z>num)                {                    next.z=now.z-num;                    next.x=a;                }                else                {                    next.x=now.x+now.z;                    next.z=0;                }                if(!vis[next.x][next.y][next.z])                {                    vis[next.x][next.y][next.z]=1;                    que.push(next);                }            }        }    }}int main(){    while(scanf("%d%d%d",&a,&b,&c)>0)    {        if(a+b+c==0)break;        if(a%2)//剪枝        {            puts("NO");            continue;        }        memset(vis,0,sizeof(vis));        flag=0;        bfs();        if(!flag)puts("NO");    }}
View Code

 

hdu1495(bfs)