POJ3414 Pots（BFS+记忆路径）

January 21, 2016

题目链接

题意：输入 a、b、c，a 和 b 分别是两个杯子的容量。根据给的规则倒水，问如何倒水才能让其中一个杯子中水的体积等于 c。

思路：BFS+保存路径。用结构体中的二维数组保存路径。

#include<iostream>
#include<cmath>
#include<queue>
#include<cstring>
#include<string>
#include<set>
#include<cstdio>
#include<algorithm>
using namespace std;
int a, b, c;
bool vis[105][105];
struct node{
    int a, b, step;
    char s[206][15];
};
void bfs(){
    queue<node> q;
    node n1, n2, n3;
    n1.a = 0; n1.b = 0; n1.step = 0;
    vis[0][0] = 1;
    q.push(n1);
    while(!q.empty()){
        n2 = q.front();
        q.pop();
        for(int i = 0; i < 6; i++){
            if(i == 0){
                n3.a = a;
                n3.b = n2.b;
                strcpy(n3.s[n2.step], "FILL(1)");
            }
            if(i == 1){
                n3.a = n2.a;
                n3.b = b;
                strcpy(n3.s[n2.step], "FILL(2)");
            }
            if(i == 2){
                int cha = b-n2.b;
                if(n2.a <= cha){
                    n3.a = 0;
                    n3.b = n2.b+n2.a;
                }else{
                    n3.a = n2.a-cha;
                    n3.b = b;
                }
                strcpy(n3.s[n2.step], "POUR(1,2)");
            }
            if(i == 3){
                int cha = a-n2.a;
                if(n2.b <= cha){
                    n3.b = 0;
                    n3.a = n2.a+n2.b;
                }else{
                    n3.b = n2.b-cha;
                    n3.a = a;
                }
                strcpy(n3.s[n2.step], "POUR(2,1)");
            }
            if(i == 4){
                n3.a = 0;
                n3.b = n2.b;
                strcpy(n3.s[n2.step], "DROP(1)");
            }
            if(i == 5){
                n3.b = 0;
                n3.a = n2.a;
                strcpy(n3.s[n2.step], "DROP(2)");
            }

            for(int i = 0; i < n2.step; i++){
                strcpy(n3.s[i], n2.s[i]);
            }
            n3.step = n2.step+1;
            if(n3.a == c || n3.b == c){
                cout << n3.step << endl;
                for(int i = 0; i < n3.step; i++){
                    //cout << "a: " <<n3.a << " " << "b:" << n3.b << endl;
                    cout << n3.s[i] << endl;
                }
                return;
            }

            if(!vis[n3.a][n3.b]){
                vis[n3.a][n3.b] = 1;
                q.push(n3);
            }

        }
    }
    cout << "impossible" << endl;
}
int main(){
    //freopen("a.txt", "r", stdin);
    while(scanf("%d %d %d", &a, &b, &c) != EOF){
        memset(vis, 0, sizeof(vis));
        bfs();
    }
    return 0;
}