[POJ] 1606 Jugs(BFS+路径输出)

题目地址：http://poj.org/problem?id=1606

广度优先搜索的经典问题，倒水问题。算法不需要多说，直接BFS，路径输出采用递归。最后注意是Special Judge

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#include<queue>

using namespace std;

const int K=;

queue<int> Q;

int c[K][K],ca,cb,N,ax,bx;

char map[][]={

    {"fill A"},

    {"fill B"},

    {"empty A"},

    {"empty B"},

    {"pour A B"},

    {"pour B A"}

};

struct node {

    int x,y,step;

} d[K][K];

void init()

{

    memset(c,,sizeof(c));

    memset(d,,sizeof(d));

}

void print(int xa,int xb)

{

    if(xa== && xb==) return ;

    print(d[xa][xb].x,d[xa][xb].y);

    printf("%s\n",map[d[xa][xb].step]);

}

void bfs(int cax,int cbx,int N)

{

    while(!Q.empty()) Q.pop();

    c[][]=;

    Q.push(cax);Q.push(cbx);

    while(!Q.empty()) {

        int xa=Q.front(); Q.pop();

        int xb=Q.front(); Q.pop();

        if(xb==N ) {

                print(xa,xb);

                printf("success\n");

                break;

        }

        if(!c[ca][xb]){

            c[ca][xb]=;

            d[ca][xb].x=xa;

            d[ca][xb].y=xb;

            d[ca][xb].step=;

            Q.push(ca);

            Q.push(xb);

        }

        if(!c[xa][cb]){

            c[xa][cb]=;

            d[xa][cb].x=xa;

            d[xa][cb].y=xb;

            d[xa][cb].step=;

            Q.push(xa);

            Q.push(cb);

        }

        if(!c[][xb]){

            c[][xb]=;

            d[][xb].x=xa;

            d[][xb].y=xb;

            d[][xb].step=;

            Q.push();

            Q.push(xb);

        }

        if(!c[xa][]){

            c[xa][]=;

            d[xa][].x=xa;

            d[xa][].y=xb;

            d[xa][].step=;

            Q.push(xa);

            Q.push();

        }

        if(xa<=cb-xb){

            if(!c[][xb+xa]){

                c[][xb+xa]=;

                d[][xb+xa].x=xa;

                d[][xb+xa].y=xb;

                d[][xb+xa].step=;

                Q.push();

                Q.push(xb+xa);

            }

        } else {

            if(xa-(cb-xb)>= && !c[xa-(cb-xb)][cb]){

                c[xa-(cb-xb)][cb]=;

                d[xa-(cb-xb)][cb].x=xa;

                d[xa-(cb-xb)][cb].y=xb;

                d[xa-(cb-xb)][cb].step=;

                Q.push(ca-(cb-xb));

                Q.push(cb);

            }

        }

        if(xb<=ca-xa){

            if(!c[xa+xb][]){

                c[xa+xb][]=;

                d[xa+xb][].x=xa;

                d[xa+xb][].y=xb;

                d[xa+xb][].step=;

                Q.push(xa+xb);

                Q.push();

            }

        } else {

            if(xb-(ca-xa)>= && !c[ca][xb-(ca-xa)]){

                c[ca][xb-(ca-xa)]=;

                d[ca][xb-(ca-xa)].x=xa;

                d[ca][xb-(ca-xa)].y=xb;

                d[ca][xb-(ca-xa)].step=;

                Q.push(ca);

                Q.push(xb-(ca-xa));

            }

        }

    }

}

int main()

{

    while(~scanf("%d%d%d",&ca,&cb,&N)){

          init();

          bfs(,,N);

    }

    return ;

}