【POJ3414】Pots

本题知识点：宽度优先搜素 + 字符串

题意很简单，如何把用两个杯子，装够到第三个杯子的水。

操作有六种，这样就可以当作是bfs的搜索方向了

// FILL(1) 把第一个杯子装满

// FILL(2) 把第二个杯子装满

// POUR(1,2) 把第一个杯子的水倒进第二个杯子

// POUR(2,1) 把第二个杯子的水倒进第一个杯子

// DROP(1) 把第一个杯子的水都倒掉

// DROP(2) 把第二个杯子的水都倒掉

本题的难点是如何记录路径，我们可以用一个巧妙的方法去解决掉，详细请看代码

// POJ 3414

#include<iostream>

#include<cstdio>

#include<string>

#include<queue>

using namespace std;

bool take[102][102], ok;

int A, B, C;

struct node{

    string str;

    int l, r, pla[102], cnt; // cnt 记录有多少条路径

};

queue<node> que;

string str[] = {

    "FILL(1)",

    "FILL(2)",

    "POUR(1,2)",

    "POUR(2,1)",

    "DROP(1)",

    "DROP(2)"

};

void show(int len, int pla[]){

    printf("%d\n", len);

    for(int i = 1; i <= len; i++){

        cout << str[pla[i]] << endl;

    }

}

void bfs(){

    ok = false;

    take[0][0] = true;

    node a;

    a.str = "NONE";

    a.l = a.r = a.cnt = 0;

    que.push(a);

    while(!que.empty()){

        node next, now = que.front(); que.pop();

//        cout << now.str << " ";

//        printf("l:%d r:%d cnt:%d\n", now.l, now.r, now.cnt);

//        show(now.cnt, now.pla);

//        cout << endl;

        if(now.l == C || now.r == C){

            show(now.cnt, now.pla);

            ok = true;

            break;

        }

        // FILL(1)

        if(now.l < A && !take[A][now.r]){

            next.str = str[0];

            next.l = A;

            next.r = now.r;

            // 这句循环是为了保存之前的路径 下同

            for(int i = 1; i <= now.cnt; i++){

                next.pla[i] = now.pla[i];

            }

            next.pla[now.cnt + 1] = 0;

            next.cnt = now.cnt + 1;

            take[A][now.r] = true;

            que.push(next);

        }

        // FILL(2)

        if(now.r < B && !take[now.l][B]){

            next.str = str[1];

            next.l = now.l;

            next.r = B;

            for(int i = 1; i <= now.cnt; i++){

                next.pla[i] = now.pla[i];

            }

            next.pla[now.cnt + 1] = 1;

            next.cnt = now.cnt + 1;

            take[now.l][B] = true;

            que.push(next);

        }

        // POUR(1, 2)

        if(0 < now.l && now.r < B){

            int R = now.l + now.r >= B ? B : now.l + now.r;

            int L = R - now.r >= now.l ? 0 : now.l - (R - now.r);

            if(!take[L][R]){

                next.str = str[2];

                next.l = L;

                next.r = R;

                for(int i = 1; i <= now.cnt; i++){

                    next.pla[i] = now.pla[i];

                }

                next.pla[now.cnt + 1] = 2;

                next.cnt = now.cnt + 1;

                take[L][R] = true;

                que.push(next);

            }

        }

        // POUR(2,1)

        if(now.l < A && 0 < now.r){

            int L = now.l + now.r >= A ? A : now.l + now.r;

            int R = L - now.l >= now.r ? 0 : now.r - (L - now.l);

            if(!take[L][R]){

                next.str = str[3];

                next.l = L;

                next.r = R;

                for(int i = 1; i <= now.cnt; i++){

                    next.pla[i] = now.pla[i];

                }

                next.pla[now.cnt + 1] = 3;

                next.cnt = now.cnt + 1;

                take[L][R] = true;

                que.push(next);

            }

        }

        // DROP(1)

        if(!take[0][now.r]){

            next.str = str[4];

            next.l = 0;

            next.r = now.r;

            for(int i = 1; i <= now.cnt; i++){

                next.pla[i] = now.pla[i];

            }

            next.cnt = now.cnt + 1;

            next.pla[now.cnt + 1] = 4;

            take[0][now.r] = true;

            que.push(next);

        }

        // DROP(2)

        if(!take[now.l][0]){

            next.str = str[5];

            next.l = now.l;

            next.r = 0;

            for(int i = 1; i <= now.cnt; i++){

                next.pla[i] = now.pla[i];

            }

            next.cnt = now.cnt + 1;

            next.pla[now.cnt + 1] = 5;

            take[now.l][0] = true;

            que.push(next);

        }

    }

    if(!ok) printf("impossible\n");

}

int main()

{

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

    bfs();

    return 0;

}

巴特西

【POJ3414】Pots

最新文章

热门文章