美文网首页
POJ-3414 倒水

POJ-3414 倒水

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

题目大意

给两个空杯子,告诉我们杯子的容量,然后给出几种操作。
操作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");
    }
}

相关文章

  • POJ-3414 倒水

    题目大意 给两个空杯子,告诉我们杯子的容量,然后给出几种操作。操作1 : DROP(x) 意思是将x杯子中的水杯...

  • 倒水

    某天午后。 浩宝又尿床了。 醒来,生气说到: 谁把水到我身上了。。。 惹得多多姐姐现在还拿此事时不时取笑他。

  • 倒水

    年前,小姑和表哥来我家做客了。大概一年没见小姑了,今天见到也格外的亲切,小姑夫去年因病去世,小姑一年里老了不少。...

  • 倒水

    好久没有这么累了。 不是码字累,而是心累。心里似装了好多好多的心事,想把它渲泄出来,但又不知从何说起。 有人说我矫...

  • 倒水

    一壶水开了, 要倒入瓶中。 开始时水满, 需远离瓶口, 方能水流大。 到后来水少, 反而要靠近, 直到水流尽。 你...

  • 倒水

    本科毕业那年,他在运维部干了半年,调到市场部。这是总公司对于校招人员的普遍培养方法,先在各个大部门待一遍,熟悉整个...

  • “倒水”

    ——选自个人旧作《教育行思录》 怎样倒桶装水,说的是不用饮水机或其它设备,就直接从桶里向外倒。 办公室里的饮水机坏...

  • 倒水

    文/四年级六班赵俪菲 上午第二节课,大张老师让张金阳同学去倒杯水,要求半凉半热。等他回来后递到大张老师...

  • 倒水

    倒水 陈庄镇中心小学四(6)班 李茂旭 今天上午上语文课的时候,大张老师让张金阳同学去倒水。大张老师说:“一定要半...

  • 倒水

    倒水 作者:利津县陈庄镇中心小学四年级六班张鑫卉 今天上午第二节课,大张老师让张金阳去给他倒一杯水,张金阳拿上杯子...

网友评论

      本文标题:POJ-3414 倒水

      本文链接:https://www.haomeiwen.com/subject/tdvinttx.html