poj 3414 Pots

http://poj.org/problem?id=3414
        
          
          while(scanf("%d%d%d",&A,&B,&C)!=EOF)
             Output Limit Exceeded
#include<iostream>

#include<string>

#include<string.h>

#include<queue>

#include<stdio.h>

#include<map>



using namespace std;

const int N=100001;

int go[6]={-1,-2,-3,1,2,3};

int a[N];

int b[N];

int pre[N];

int type[N];

bool had[105][105];

int I,K,J;

int anstype[N];

int ans,nd;

int A,B,C;

bool ok(int a1,int b1,int i)

{

    //cout<<a1<<" "<<b1<<" "<<i<<endl;

    int l1,l2;

    if(i==-1)

    {

       l1=A;l2=b1;

    }else

    if(i==-2)

    {

       l1=0;l2=b1;

    }else

    if(i==-3)

    {

        l1=min(A,a1+b1);l2=max(0,a1+b1-A);

    }else

    if(i==1)

    {

       l1=a1;l2=B;

    }else

    if(i==2)

    {

       l1=a1;l2=0;

    }else

    {

       l2=min(B,a1+b1);l1=max(0,a1+b1-B);

    }

    if(had[l1][l2])

    return false;

    had[l1][l2]=true;

    type[J]=i;

    pre[J]=I;

    //cout<<l1<<" "<<l2<<endl;

    a[J]=l1;b[J]=l2;++J;

    if(l1==C||l2==C)

    return true;

    return false;



}

void bfs(int k)

{//cout<<k<<endl;

    if(K==J)

    return;

    K=J;

    for(;I<K;++I)

    {

        for(int i=0;i<6;++i)

        if(ok(a[I],b[I],go[i]))

        {

            ans=k;nd=J-1;

            return;

        }

    }

    bfs(k+1);

}

void print()

{

    int i=ans;

    int l=nd;

    while(l!=0)

    {

        anstype[i]=type[l];

        l=pre[l];

        --i;

    }

    for(i=1;i<=ans;++i)

    {

        if(anstype[i]==-1)

        printf("FILL(1)
");

        if(anstype[i]==-2)

        printf("DROP(1)
");

        if(anstype[i]==-3)

        printf("POUR(2,1)
");

        if(anstype[i]==1)

        printf("FILL(2)
");

        if(anstype[i]==2)

        printf("DROP(2)
");

        if(anstype[i]==3)

        printf("POUR(1,2)
");

    }

}

int main()

{



        scanf("%d%d%d",&A,&B,&C);

        memset(had,false,sizeof(had));

        had[0][0]=true;

        a[0]=0;b[0]=0;

        pre[0]=0;

        type[0]=0;

        I=K=0;J=1;

        ans=-1;

        bfs(1);

        if(ans==-1)

        {

            printf("impossible
");

        }

        else

        {

            printf("%d
",ans);

            print();

        }

        return 0;

}