首页 > 代码库 > BFS/poj 3414 pots

BFS/poj 3414 pots

#include<cstdio>#include<queue>#include<cstring>using namespace std;struct point{    int a,b;    int step;    int way[110];};int aa,bb,cc;int v[110][110];void bfs(){    memset(v,0,sizeof(v));    queue<point>que;    point now,next;    now.a=0;    now.b=0;    now.step=0;    v[0][0]=true;    que.push(now);    while (!que.empty())    {        now=que.front();        que.pop();        if (now.a==cc || now.b==cc)        {            printf("%d\n",now.step);            for (int i=1;i<=now.step;i++)            {                if (now.way[i]==1) printf("FILL(1)\n");                if (now.way[i]==2) printf("FILL(2)\n");                if (now.way[i]==3) printf("DROP(1)\n");                if (now.way[i]==4) printf("DROP(2)\n");                if (now.way[i]==5) printf("POUR(1,2)\n");                if (now.way[i]==6) printf("POUR(2,1)\n");            }            return ;        }        //FILL A 111111111        if (now.a!=aa)        {            next=now;            next.a=aa;            next.b=now.b;            if (!v[next.a][next.b])            {                v[next.a][next.b]=1;                next.step=now.step+1;                next.way[next.step]=1;                que.push(next);            }        }        //FILL B 2222222222        if (now.b!=bb)        {            next=now;            next.a=now.a;            next.b=bb;            if (!v[next.a][next.b])            {                v[next.a][next.b]=1;                next.step=now.step+1;                next.way[next.step]=2;                que.push(next);            }        }        //DROP A 3333333333        if (now.a!=0)        {            next=now;            next.a=0;            next.b=now.b;            if (!v[next.a][next.b])            {                v[next.a][next.b]=1;                next.step=now.step+1;                next.way[next.step]=3;                que.push(next);            }        }        //DROP B 444444444444        if (now.b!=0)        {            next=now;            next.a=now.a;            next.b=0;            if (!v[next.a][next.b])            {                v[next.a][next.b]=1;                next.step=now.step+1;                next.way[next.step]=4;                que.push(next);            }        }        //pour(1,2)  5555555555555        if (now.a!=0)        {            if (now.a>=bb-now.b)  //a 倒满 b            {                next=now;                next.a=now.a-(bb-now.b);                next.b=bb;                if (!v[next.a][next.b])                {                    v[next.a][next.b]=1;                    next.step=now.step+1;                    next.way[next.step]=5;                    que.push(next);                }            }else if (now.a<bb-now.b)   //a 空了  没倒满 b            {                next=now;                next.a=0;                next.b=now.b+now.a;                if (!v[next.a][next.b])                {                    v[next.a][next.b]=1;                    next.step=now.step+1;                    next.way[next.step]=5;                    que.push(next);                }            }        }        //POUR(2,1)  6666666666666        if (now.b!=0)        {            if (now.b>=aa-now.a)            {                next=now;                next.a=aa;                next.b=now.b-(aa-now.a);                if (!v[next.a][next.b])                {                    v[next.a][next.b]=1;                    next.step=now.step+1;                    next.way[next.step]=6;                    que.push(next);                }            }else if (now.b<aa-now.a)            {                next=now;                next.a=now.a+now.b;                next.b=0;                if (!v[next.a][next.b])                {                    v[next.a][next.b]=1;                    next.step=now.step+1;                    next.way[next.step]=6;                    que.push(next);                }            }        }    }    printf("impossible\n");}int main(){    scanf("%d%d%d",&aa,&bb,&cc);    bfs();    return 0;}

 

BFS/poj 3414 pots