POJ - 3414 Pots BFS + 保存(打印)路径

这道题我都第一反应就是HDU的一道题叫非常可乐,所以就模仿着敲了,但是有个难点就是要正着输出操作步骤,哇,这个卡了好久,还是没想出来,最后在网上找了一个题解,看了一下它的路径是怎样保存下来并输出,于是就模仿着它的方法套到我写的里面就A了.(那个输出路径那个真巧!)
代码

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<set>
#include<queue>
#include<stack>
#include<map>
#include<cstdlib>
#define CLR(x) memset(x,0,sizeof(x))
#define ll long long int
#define PI acos(-1.0)
#define db double
using namespace std;
const int maxn=1e2+5;
const int eps=1e-6;
const int inf=1e9;
const ll INF=1e15;
int cas=1;
int a,b,c;
int flag=0;

int vis[maxn][maxn];
char str[10][10]={"","FILL(1)","FILL(2)","DROP(1)","DROP(2)","POUR(1,2)","POUR(2,1)"};
//对应步骤的操作.

struct node
{
    int x,y;
    int step;
    char s[1000];
};

void bfs()//思维要清楚啊,不要被自己绕晕了就是了.
{
    queue<node>q;
    node p,k;
    p.x=0,p.y=0,p.step=0,p.s[0]='0';
    vis[p.x][p.y]=1;
    q.push(p);
    while(!q.empty()){
        k=q.front();
        q.pop();
        if(k.x==c || k.y==c){
            flag=1;
            printf("%d\n",k.step);
            for(int i=0;i<k.step;i++){
                printf("%s\n",str[k.s[i]-'0']);
            }
            return ;
        }
        //printf("%d %d\n",k.x,k.y);
        if(k.x<a){     //把第一个瓶子装满
            p.x=a;
            p.y=k.y;
            p.step=k.step+1;
            strcpy(p.s,k.s);
            p.s[k.step]=1+'0';
            if(!vis[p.x][p.y]){
                vis[p.x][p.y]=1;
                q.push(p);
                //printf("%d %d 1\n",p.x,p.y);
            }
        }
        if(k.y<b){      //把第二个瓶子装满
            p.y=b;
            p.x=k.x;
            p.step=k.step+1;
            strcpy(p.s,k.s);
            p.s[k.step]=2+'0';
            if(!vis[p.x][p.y]){
                vis[p.x][p.y]=1;
                q.push(p);
                //printf("%d %d 2\n",p.x,p.y);
            }
        }
        if(k.x!=0){     //把第一个瓶子倒了
            p.x=0;
            p.y=k.y;
            p.step=k.step+1;
            strcpy(p.s,k.s);
            p.s[k.step]=3+'0';
            if(!vis[p.x][p.y]){
                vis[p.x][p.y]=1;
                q.push(p);
                //printf("%d %d 3\n",p.x,p.y);
            }
        }
        if(k.y!=0){      //把第二个瓶子倒了
            p.y=0;
            p.x=k.x;
            p.step=k.step+1;
            strcpy(p.s,k.s);
            p.s[k.step]=4+'0';
            if(!vis[p.x][p.y]){
                vis[p.x][p.y]=1;
                q.push(p);
                //printf("%d %d 4\n",p.x,p.y);
            }
        }
        if(k.x!=0 && k.y<b){    //把第一个倒进第二个
            if(b-k.y>=k.x){
                p.y=k.x+k.y;
                p.x=0;
            }
            else{
                p.x=k.x+k.y-b;
                p.y=b;
            }
            //printf("%d %d\n",p.x,p.y);;
            p.step=k.step+1;
            strcpy(p.s,k.s);
            p.s[k.step]=5+'0';
            if(!vis[p.x][p.y]){
                vis[p.x][p.y]=1;
                q.push(p);
                //printf("%d %d 5\n",p.x,p.y);
            }
        }
        if(k.y!=0 && k.x<a){    //把第二个倒进第一个.
            if(a-k.x>=k.y){
                p.x=k.x+k.y;
                p.y=0;
            }
            else{
                p.y=k.x+k.y-a;
                p.x=a;
            }
            p.step=k.step+1;
            strcpy(p.s,k.s);
            p.s[k.step]=6+'0';
            if(!vis[p.x][p.y]){
                vis[p.x][p.y]=1;
                q.push(p);
                //printf("%d %d 6\n",p.x,p.y);
            }
        }
    }
}
int main()
{

    scanf("%d %d %d",&a,&b,&c);
    CLR(vis);
    bfs();
    if(!flag)
        printf("impossible\n");

}