POJ3414简单dfs+记录路径

#include <iostream>
#include <algorithm>
using namespace std;
#include <cstring>
#include <queue>
#include <stack>
int vis[500][500];
int a,b,ans,c;
struct zhuangTai
{
    int a,b,step,flag;
    zhuangTai *pre;
};
zhuangTai t[400];
zhuangTai now;
queue <zhuangTai> record;
stack <int > outP;
void bfs()
{
    now.a=0;
    now.b=0;
    now.pre=NULL;
    now.flag=0;
    now.step=0;
    record.push(now);
    vis[0][0]=1;
    int count=-1;
    while(!record.empty())
    {
        count++;
        t[count]=record.front();
        record.pop();
        for(int i=1;i<=6;i++)
        {
            switch(i)
            {
            case 1:
                now.a=a;
                now.b=t[count].b;
                now.flag=1;
                break;
                case 2:
                now.a=t[count].a;
                now.b=b;
                now.flag=2;
                break;
                case 3:
                    now.a=0;
                    now.b=t[count].b;
                    now.flag=3;
                    break;
                    case 4:
                    now.a=t[count].a;
                    now.b=0;
                    now.flag=4;
                    break;

                    case 5:
                        if(t[count].a>b-t[count].b)
                        {
                            now.a=t[count].a-b+t[count].b;
                            now.b=b;
                        }
                    else
                    {
                        now.a=0;
                        now.b=t[count].a+t[count].b;
                    }
                    now.flag = 5;
                    break;
                    case 6:
                        if(t[count].b>a-t[count].a)
                        {
                            now.b=t[count].b-a+t[count].a;
                            now.a=a;
                        }
                    else
                    {
                        now.b=0;
                        now.a=t[count].b+t[count].a;
                    }
                    now.flag = 6;
                    break;
            }

            if(vis[now.a][now.b])
                continue;
            vis[now.a][now.b]=1;
            now.step=t[count].step+1;
            now.pre=&t[count];
            if(now.a==c||now.b==c)
            {
                ans=now.step;
                while(now.pre)
                {
                    outP.push(now.flag);
                    now=*now.pre;
                }
                return;
            }
              record.push(now);
        }

    }
}
void print()
{
    cout<<ans<<endl;
    while(!outP.empty())
    {
        int i = outP.top();
        outP.pop();
        switch(i)
        {
            case 1:cout<<"FILL(1)"<<endl;break;
            case 2:cout<<"FILL(2)"<<endl;break;
            case 3:cout<<"DROP(1)"<<endl;break;
            case 4:cout<<"DROP(2)"<<endl;break;
            case 5:cout<<"POUR(1,2)"<<endl;break;
            case 6:cout<<"POUR(2,1)"<<endl;break;
        }
    }
}
int main()
{
    memset(vis,0,sizeof(vis));
cin>>a>>b>>c;

        ans=0;
        bfs();
        if(ans==0)
        {
            cout<<"impossible"<<endl;
        }
        else
            print();

    return 0;
}