专栏首页用户6093955的专栏Pots(POJ - 3414)【BFS 寻找最短路+路径输出】

Pots(POJ - 3414)【BFS 寻找最短路+路径输出】

Pots(POJ - 3414)

题目链接

算法

BFS

1.这道题问的是给你两个体积分别为A和B的容器,你对它们有三种操作,一种是装满其中一个瓶子,另一种是把其中一个瓶子的水都倒掉,还有一种就是把其中一个瓶子的水导入另一个瓶子中(可能会有剩余)。最后让你输出在能够得出体积为C的水的情况下操作的最小次数并且把过程输出。如果无法得出体积为C的水,则输出“impossible”。

2.这个题主要涉及两个点,一个是求出最小次数,还有一个就是把路径输出。对于这种有目标值的求最小次数问题,我们可以使用bfs解决。初始状态是两个瓶子都为空,最终状态是其中一个瓶子中的水的容量达到了目标值C。在每个状态下可以对瓶子进行上面描述的三种操作,细分下来其实只有6种操作,分别是:

  • 将A瓶子装满水
  • 将B瓶子装满水
  • 将A瓶子中的水倒入B瓶子中
  • 将B瓶子中的倒入A瓶子中
  • 将A瓶子中的水全部抽走
  • 将B瓶子中的水全部抽走

我们可以把每种状态都放入到队列中,当到达某种状态时,就分别执行上面6个操作,同时需要注意做好每种状态的标记,避免重复。

3.为了获得路径,我们可以把每次将新的状态插入队列中的同时用数组记录,可以用结构体来存放每个状态,该结构体中除了当前A瓶和B瓶中水的容量这两种属性外,还要有它本身在数组中的下标id,父状态在数组中的下标pre,到达此状态时的最小步数steps。由于bfs的特殊性,我们可以认为当达到目标值时的steps为最小最优的(至于为什么是最优的,我们可以简单的想bfs因为是一层一层的搜索的,所以可以认为第一个到达目标值的层数是最小的,当然前提是代价是一样的,比如这里每执行一步都表示一次,故可以用bfs实现,而如果执行每种操作的代价不同,就不能用bfs来实现了)。

C++代码

#include<iostream>
#include<queue>
#include<stack>
#include<cstdio>
using namespace std;
const int N = 1e6 + 10, M = 1e3;
int a, b, c;
bool st[M][M];
struct Status{
    int ca, cb, pre;
    int ope;    //1表示装满A,2表示装满B,3表示A倒入B,4表示B倒入A,5表示倒掉A,6表示倒掉B
    int steps;
    int id;
    Status(){
        ca = 0, cb = 0, pre = -1;
        ope = -1;
        steps = 0;
        id = 0;
    }
}s[N];
int cnt;
//装满A
void fullA(Status& t)
{
    t.ca = a;
    t.ope = 1;
    t.steps++;
    t.id = cnt;
    //s[cnt++] = t;
}
//倒掉A
void pourA(Status& t)
{
    t.ca = 0;
    t.ope = 5;
    t.steps++;
    t.id = cnt;
    //s[cnt++] = t;
}
//装满B
void fullB(Status& t)
{
    t.cb = b;
    t.ope = 2;
    t.steps++;
    t.id = cnt;
    //s[cnt++] = t;
}
//倒掉B
void pourB(Status& t)
{
    t.cb = 0;
    t.ope = 6;
    t.steps++;
    t.id = cnt;
   // s[cnt++] = t;
}
//A倒入B
void pourA_B(Status& t)
{
    if(t.ca >= b - t.cb)
    {
        t.ca -= b - t.cb;
        t.cb = b;
    }
    else
    {
        t.cb += t.ca;
        t.ca = 0;
    }
    t.ope = 3;
    t.steps++;
    t.id = cnt;
    //s[cnt++] = t;
}
//B倒入A
void pourB_A(Status& t)
{
    if(t.cb >= a - t.ca)
    {
        t.cb -= a - t.ca;
        t.ca = a;
    }
    else
    {
        t.ca += t.cb;
        t.cb = 0;
    }
    t.ope = 4;
    t.steps++;
    t.id = cnt;
    //s[cnt++] = t;
}
void print(Status t)
{
    cout << t.steps << endl;
    stack<Status> sta;
    sta.push(t);
    while(true)
    {
        if(t.pre == -1) break;
        t = s[t.pre];
        sta.push(t);
    }
    while(sta.size())
    {
        Status tmp = sta.top();
        sta.pop();
        if(tmp.ope == 1)
            puts("FILL(1)");
        else if(tmp.ope == 2)
            puts("FILL(2)");
        else if(tmp.ope == 3)
            puts("POUR(1,2)");
        else if(tmp.ope == 4)
            puts("POUR(2,1)");
        else if(tmp.ope == 5)
            puts("DROP(1)");
        else if(tmp.ope == 6)
            puts("DROP(2)");
    }
}
void bfs()
{
    Status tmp;
    queue<Status> que;
    que.push(tmp);
    st[tmp.ca][tmp.cb] = true;
    s[cnt++] = tmp;
    while(que.size())
    {
        tmp = que.front();
        que.pop();
        //cout << "***" << tmp.ca << ", " << tmp.cb << endl;
        if(tmp.ca == c || tmp.cb == c)
        {
            //cout << "**end** " << tmp.ca << " , " << tmp.cb << ", " << tmp.pre << endl;
            //打印输出
            print(tmp);
            return ;
        }
        //循环那六种情况
        for(int i = 1; i <= 6; i++)
        {
            Status tmp1 = tmp;
            //cout << "tmp*** " << tmp.ca << ", " << tmp.cb << endl;
            if(i == 1)
            {
                if(tmp1.ca == a) continue;
                fullA(tmp1);
                if(!st[tmp1.ca][tmp1.cb])
                {
                    tmp1.pre = tmp.id;
                    st[tmp1.ca][tmp1.cb] = true;
                    que.push(tmp1);
                    s[cnt++] = tmp1;
                    //cout << "tmp1**1* " << tmp1.ca << ", " << tmp1.cb << endl;
                }

            }
            else if(i == 2)
            {
                if(tmp1.cb == b) continue;
                fullB(tmp1);
                if(!st[tmp1.ca][tmp1.cb])
                {
                    tmp1.pre = tmp.id;
                    st[tmp1.ca][tmp1.cb] = true;
                    que.push(tmp1);
                    s[cnt++] = tmp1;
                    //cout << "tmp1**2* " << tmp1.ca << ", " << tmp1.cb << endl;
                }

            }
            else if(i == 3)
            {
                if(!(tmp1.ca)) continue;
                pourA_B(tmp1);
                if(!st[tmp1.ca][tmp1.cb])
                {
                    tmp1.pre = tmp.id;
                    st[tmp1.ca][tmp1.cb] = true;
                    que.push(tmp1);
                    s[cnt++] = tmp1;
                    //cout << "tmp1**3* " << tmp1.ca << ", " << tmp1.cb << endl;
                }

            }
            else if(i == 4)
            {
                if(!(tmp1.cb)) continue;
                pourB_A(tmp1);
                if(!st[tmp1.ca][tmp1.cb])
                {
                    tmp1.pre = tmp.id;
                    st[tmp1.ca][tmp1.cb] = true;
                    que.push(tmp1);
                    s[cnt++] = tmp1;
                    //cout << "tmp1**4* " << tmp1.ca << ", " << tmp1.cb << endl;
                }

            }
            else if(i == 5)
            {
                if(!(tmp1.ca)) continue;
                pourA(tmp1);
                if(!st[tmp1.ca][tmp1.cb])
                {
                    tmp1.pre = tmp.id;
                    st[tmp1.ca][tmp1.cb] = true;
                    que.push(tmp1);
                    s[cnt++] = tmp1;
                    //cout << "tmp1**5* " << tmp1.ca << ", " << tmp1.cb << endl;
                }

            }
            else if(i == 6)
            {
                if(!(tmp1.cb)) continue;
                pourB(tmp1);
                if(!st[tmp1.ca][tmp1.cb])
                {
                    tmp1.pre = tmp.id;
                    st[tmp1.ca][tmp1.cb] = true;
                    que.push(tmp1);
                    s[cnt++] = tmp1;
                    //cout << "tmp1**6* " << tmp1.ca << ", " << tmp1.cb << endl;
                }

            }
        }
    }
    puts("impossible");
}

int main()
{
    cin >> a >> b >> c;
    bfs();
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 层序遍历

    _DIY
  • sendRedirect()和forward()方法的区别

    虽然二者都可以实现获取相应的url资源,但首先要注意的是,重定向由sendRedirect来实现,请求转发由forward来实现。

    _DIY
  • Sticks(UVA - 307)【DFS+剪枝】

    1.这道题题意就是说原本有一些等长的木棍,后来把它们切割,切割成一个个最长为50单位长度的小木棍,现在想让你把它们组合成一个个等长的大木棍,要求这个拼接成的大木...

    _DIY
  • 巧用MOOC组合掌握机器学习

    咱们不提CES 2017上激动人心的自动驾驶产品(估计七八年之后你的驾驶证就可以扔掉了),也不细讲《最强大脑》节目里人类精英在图像识别环节被碾压(这曾经是人类可...

    王树义
  • 入门 node.js 你必须知道的那些事

    exports 是 module.exports 的一个引用,意思就是指向同一块内存地址,node 中真正生效的是 module.exports, 修改 exp...

    IT派
  • 关于Transformer,面试官们都怎么问

    前些时间,赶完论文,开始对 Transformer、GPT、Bert 系列论文来进行仔仔细细的研读,然后顺手把站内的相关问题整理了一下,但是发现站内鲜有回答仔细...

    kaiyuan
  • 【NLP】关于Transformer,面试官们都怎么问

    前些时间,赶完论文,开始对 Transformer、GPT、Bert 系列论文来进行仔仔细细的研读,然后顺手把站内的相关问题整理了一下

    yuquanle
  • 资源 | Hinton、LeCun、吴恩达......不容错过的15大机器学习课程都在这儿了

    翻译 | AI科技大本营 参与 | 刘畅 编辑 | Donna 之前,我们推送了由sky2learn整理的15大深度学习课程。这次,我们整理了15个必看的机器学...

    AI科技大本营
  • Go Web编程--使用Go语言创建静态文件服务器

    上篇关于Go模板库应用实践的文章最后我们留下一个问题,页面模板是通过 CDN引用的 BootStrap的 css, js文件。到目前位置我们的服务器还无法伺服客...

    KevinYan
  • Jquery $.extend的重载方法详述

    1 $.extend(result,item1,item2,item3,........)  -这个重载方法主要是用来合并,将所有的参数都合并到result中,...

    郑小超.

扫码关注云+社区

领取腾讯云代金券