poj-3414

poj 3414

bfs搜索所有情况

当其中一个达到目标c时，返回就可以，对于所有的操作共有六种，所以在bfs中按顺序模拟六种情况就可以

#include <iostream>
#include <queue>
#include <string>
#include <cstring>
#include <cstdio>

using namespace std;

#define max 105

struct pot {
    int a, b;       // a b
    string str;        // op
    pot() = default;
    pot(int a, int b, string str) : a(a), b(b), str(str) {}
};
int a, b, c;
queue<pot> q;
bool vis[max][max];
string op[6] = {"FILL(1)", "FILL(2)", "DROP(1)", "DROP(2)", "POUR(1,2)", "POUR(2,1)"};
string order[6] = {"0", "1", "2", "3", "4", "5"};

bool bfs() {
    memset(vis, false, sizeof(vis));
    q.push(pot(0, 0, ""));
    while(!q.empty()) {
        pot t = q.front();
        q.pop();

        if(vis[t.a][t.b]) continue;
        vis[t.a][t.b] = true;

        if(t.a == c || t.b == c) {
            int len = t.str.size();
            printf("%d\n", len);
            for(int i = 0;i < len; ++i) {
                printf("%s\n", op[t.str[i] - '0'].c_str());
            }
            return true;
        }

        for(int i = 0;i < 6; ++i) {
            pot op = t;

            switch(i) {
            case 0 :        // op fill(1) ...
                op.a = a;
                break;
            case 1:
                op.b = b;
                break;
            case 2:
                op.a = 0;
                break;
            case 3:
                op.b = 0;
                break;
            case 4:
                if(op.a + op.b >= b){ op.b = b;  op.a = t.a + t.b - b;}
                else {op.b = t.a + t.b; op.a = 0;}
                break;
            case 5:
                if(op.a + op.b >= a) { op.a = a; op.b = t.a + t.b - a;}
                else {op.a = t.a + t.b; op.b = 0;}
                break;
            default:
                break;
            }
            op.str = t.str + order[i];
            q.push(op);
        }
    }
    return false;
}

int main() {
    while(~scanf("%d%d%d",&a, &b, &c)) {
        bool flag = bfs();
        if(!flag) printf("impossible\n");
    }
    return 0;
}