#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
struct node
{
    int k;
    int a,b;
    int length;
    int pre;
}f[10000];
int A,B,C;
int step,num;
int visit[105][105];
node start;
int bfs()
{
    memset(visit,0,sizeof(visit));
    int rear=0;
    int front=1;
    f[rear]=start;
    visit[start.a][start.b]=1;
    while(rear!=front)
    {
        node p=f[rear];
       // printf("%d %d\n",p.a,p.b);
        if(p.a==C || p.b==C)
        {
            step=p.length;
            num=rear;
            return 1;
        }
        node q;
        q=p;
        q.a=A;
        q.length=p.length+1;
        if(!visit[q.a][q.b] && p.a!=A)
        {
            visit[q.a][q.b]=1;
            q.pre=rear;
            q.k=1;
            f[front]=q;
            front++;
        }
        q=p;
        q.b=B;
        q.length=p.length+1;
        if(!visit[q.a][q.b] && p.b!=B)
        {
            visit[q.a][q.b]=1;
            q.pre=rear;
            q.k=2;
            f[front]=q;
            front++;
        }
        q=p;
        q.a=0;
        q.length=p.length+1;
        if(!visit[q.a][q.b] && p.a!=0)
        {
            visit[q.a][q.b]=1;
            q.pre=rear;
            q.k=3;
            f[front]=q;
            front++;
        }
        q=p;
        q.b=0;
        q.length=p.length+1;
        if(!visit[q.a][q.b] && p.b!=0)
        {
            visit[q.a][q.b]=1;
            q.pre=rear;
            q.k=4;
            f[front]=q;
            front++;
        }
        if(p.a!=A && p.b!=0)
        {
            q=p;
            if(q.a+q.b>=A)
            {
                q.a=A;
                q.b=(p.a+p.b)-A;
            }
            else
            {
                q.a+=q.b;
                q.b=0;
            }
            q.length=p.length+1;
            if(!visit[q.a][q.b])
            {
                visit[q.a][q.b]=1;
                q.pre=rear;
                q.k=5;
                f[front]=q;
                front++;
            }
        }
        if(p.b!=B && p.a!=0)
        {
            q=p;
            if(q.b+q.a>=B)
            {
                q.b=B;
                q.a=(p.a+p.b)-B;

            }
            else
            {
                q.b+=q.a;
                q.a=0;
            }
            q.length=p.length+1;
            if(!visit[q.a][q.b])
            {
                visit[q.a][q.b]=1;
                q.pre=rear;
                q.k=6;
                f[front]=q;
                front++;
            }
        }
        rear++;
    }
    return 0;
}
int main()
{
    while(scanf("%d %d %d",&A,&B,&C)!=EOF)
    {
        start.a=0;
        start.b=0;
        start.pre=-1;
        start.length=0;
        int ans;
        ans=bfs();
        if(ans)
        {
            int m=num;
            printf("%d\n",step);
            int a[1000];
            int s=0;
            while(f[m].pre!=-1)
            {
                a[s++]=m;
                m=f[m].pre;
            }
           for(int i=s-1;i>=0;i--)
               {
                int k=f[a[i]].k;
                if(k==1)
                  printf("FILL(1)\n");
                else if(k==2)
                  printf("FILL(2)\n");
                else if(k==3)
                  printf("DROP(1)\n");
                else if(k==4)
                   printf("DROP(2)\n");
                else if(k==5)
                   printf("POUR(2,1)\n");
                else if(k==6)
                   printf("POUR(1,2)\n");
                m=f[m].pre;
               }


        }
        else
          printf("impossible\n");
    }
    return 0;
}

• Re:贴下代码留个纪念。 (4146) hzh19970714 2011-04-24 20:08:55