POJ-3414 倒水

作者: 四川孙一峰 | 来源:发表于2017-03-20 20:35 被阅读0次

POJ-3414 倒水
倒水
倒水
倒水
倒水
倒水
“倒水”
倒水
倒水
倒水

题目大意

给两个空杯子，告诉我们杯子的容量，然后给出几种操作。
操作1 ： DROP(x) 意思是将x杯子中的水杯倒空。
操作2 ： FILL(x) 意思是把x杯子中装满。
操作3 ： POUR(x,y) 意思是将x杯子中的水全部倒到y中去。

然后给定一个k值，问经过最小多少次操作能有一个水杯里的水有k这么多。输出操作次数及方式。
如果没法满足，输出impossible。

样例输入

3 5 4

样例输出

6
FILL(2)
POUR(2,1)
DROP(1)
POUR(2,1)
FILL(2)
POUR(2,1)

分析

这题用bfs搜一遍，不要用dfs答案其实没那么深，深搜没必要而且会炸
最麻烦的是输出路径，用爸爸儿子的办法倒着找就好了。

代码如下

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<map>
#include<cmath>
#include<queue>
#define CLR(x) memset(x,0,sizeof(x))
#define LL long long
#define debug() printf("!!!!!!!!\n");
using namespace std;

int k,con;

struct node{
    int v1,v2;
    int s1,s2;
    int id;
    int pre;
    char c[20];
}now,ans[500];

char str[1000][20];

int vis[105][105];

int bfs(){
    queue<node> q;
    q.push(now);
    while(!q.empty()){
        node r = q.front();
        q.pop();
        int tmp1 = r.s1 , tmp2 = r.s2;
        if(r.s1 == k || r.s2 == k){
            //printf("%d %d\n",r.s1,r.s2);
            //printf("r.id = %d\n",r.id);
            return r.id;
        }
//=============================================
        //DROP1;
        if(r.s1){
            r.s1 = 0;
            if(vis[r.s1][r.s2] == 0){
                vis[r.s1][r.s2] = 1;
                con++;
                ans[con] = r;
                ans[con].pre = r.id;
                ans[con].id = con;
                char c[20] = {"DROP(1)\0"};
                strcpy(ans[con].c , c);
                q.push(ans[con]);
            }
            r.s1 = tmp1;
        }
        //FILL1;
        r.s1 = r.v1;
        if(vis[r.s1][r.s2] == 0){
            vis[r.s1][r.s2] = 1;
            con++;
            ans[con] = r;
            ans[con].pre = r.id;
            ans[con].id = con;
            char c[20] = {"FILL(1)\0"};
            strcpy(ans[con].c , c);
            q.push(ans[con]);
        }
        r.s1 = tmp1;
        //POUR(1,2)
        int cha = r.v2 - r.s2 ;
        if(r.s1 >= cha){
            r.s1 -= cha;
            r.s2 = r.v2;
        }
        else{
            r.s2 += r.s1;
            r.s1 = 0;
        }
        if(vis[r.s1][r.s2] == 0){

            vis[r.s1][r.s2] = 1;
            vis[r.s1][r.s2] = 1;
            con++;
            ans[con] = r;
            ans[con].pre = r.id;
            ans[con].id = con;
            char c[20] = {"POUR(1,2)\0"};
            strcpy(ans[con].c,c);
            q.push(ans[con]);
        }
        r.s1 = tmp1;
        r.s2 = tmp2;

//=========================================
        //DROP(2)
        if(r.s2){
            r.s2 = 0;
            if(vis[r.s1][r.s2] == 0){
                vis[r.s1][r.s2] = 1;
                con++;
                ans[con] = r;
                ans[con].pre = r.id;
                ans[con].id = con;
                char c[20] = {"DROP(2)\0"};
                strcpy(ans[con].c , c);
                q.push(ans[con]);
            }
            r.s2 = tmp2;
        }
        //FILL(2)
        r.s2 = r.v2;
        if(vis[r.s1][r.s2] == 0){
            vis[r.s1][r.s2] = 1;
            con++;
            ans[con] = r;
            ans[con].pre = r.id;
            ans[con].id = con;
            char c[20] = {"FILL(2)\0"};
            strcpy(ans[con].c,c);
            q.push(ans[con]);
        }
        r.s2 = tmp2;
        //POUR(2,1)
        cha = r.v1 - r.s1 ;
        if(r.s2 >= cha){
            r.s2 -= cha;
            r.s1 = r.v1;
        }
        else{
            r.s1 += r.s2;
            r.s2 = 0;

        }
        if(!vis[r.s1][r.s2]){
            vis[r.s1][r.s2] = 1;
            vis[r.s1][r.s2] = 1;
            con++;
            ans[con] = r;
            ans[con].pre = r.id;
            ans[con].id = con;
            char c[20] = {"POUR(2,1)\0"};
            strcpy(ans[con].c , c);
            q.push(ans[con]);
        }
        r.s1 = tmp1;
        r.s2 = tmp2;
    }
    return -1;

}

int main(){
    CLR(ans);
    CLR(str);
    cin >> now.v1 >> now.v2 >> k;
    now.pre = -1;
    now.id = 0;
    now.c[0] = 0;
    CLR(vis);
    con = 0;
    int x = bfs();
    //printf("%d\n",x);
    int cnt = 0;
    if(x != -1){
         while(ans[x].pre != 0){
            strcpy(str[cnt],ans[x].c);
            x = ans[x].pre;
            cnt++;
            //printf(" x = %d , cnt = %d\n",x,cnt);
         }
         strcpy(str[cnt],ans[x].c);
         printf("%d\n",cnt+1);
         for(int i = cnt ; i >= 0 ; i--){
            printf("%s\n",str[i]);
         }
    }
    else{
        printf("impossible\n");
    }
}