Pots(DFS BFS)

news/2024/6/29 11:49:57 标签: 深度优先, 宽度优先, 算法, c++

//新生训练

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 205;
int n, m;
int l;
int A, B, C;
int dis[N][N];

struct node
{
    int px, py, op;
};

node pre[N][N];

void dfs(int x, int y)
{
    if (x == 0 && y == 0)
    {
        return;
    }
    dfs(pre[x][y].px, pre[x][y].py);
    switch (pre[x][y].op)
    {
    case 1:
        cout << "FILL(1)\n";
        break;
    case 2:
        cout << "FILL(2)\n";
        break;
    case 3:
        cout << "DROP(1)\n";
        break;
    case 4:
        cout << "DROP(2)\n";
        break;
    case 5:
        cout << "POUR(1,2)\n";
        break;
    case 6:
        cout << "POUR(2,1)\n";
    }
}

bool flag = 1;

void bfs()
{
    queue<PII> q;
    q.push(make_pair(0, 0));
    dis[0][0] = 0;
    while (!q.empty())
    {
        PII t = q.front();
        q.pop();

        int x = t.first, y = t.second;
        if (x == C || y == C)
        {
            cout << dis[x][y] << '\n';
            dfs(x, y);
            flag = 0;
            return;
        }
        int ix, iy;

        // FILL(1)
        ix = A, iy = y;
        if (dis[ix][iy] == -1)
        {
            dis[ix][iy] = dis[x][y] + 1;
            pre[ix][iy] = {x, y, 1};
            q.push(make_pair(ix, iy));
        }

        // FILL(2)
        ix = x, iy = B;
        if (dis[ix][iy] == -1)
        {
            dis[ix][iy] = dis[x][y] + 1;
            pre[ix][iy] = {x, y, 2};
            q.push(make_pair(ix, iy));
        }

        // DROP(1)
        ix = 0, iy = y;
        if (dis[ix][iy] == -1)
        {
            dis[ix][iy] = dis[x][y] + 1;
            pre[ix][iy] = {x, y, 3};
            q.push(make_pair(ix, iy));
        }

        // DROP(2)
        ix = x, iy = 0;
        if (dis[ix][iy] == -1)
        {
            dis[ix][iy] = dis[x][y] + 1;
            pre[ix][iy] = {x, y, 4};
            q.push(make_pair(ix, iy));
        }

        // POUR(1,2)
        ix = x, iy = y;
        while (ix && iy < B)
        {
            --ix;
            ++iy;
        }
        if (dis[ix][iy] == -1)
        {
            dis[ix][iy] = dis[x][y] + 1;
            pre[ix][iy] = {x, y, 5};
            q.push(make_pair(ix, iy));
        }

        // POUR(2,1)
        ix = x, iy = y;
        while (iy && ix < A)
        {
            ++ix;
            --iy;
        }
        if (dis[ix][iy] == -1)
        {
            dis[ix][iy] = dis[x][y] + 1;
            pre[ix][iy] = {x, y, 6};
            q.push(make_pair(ix, iy));
        }
    }
}

void solve()
{
    memset(dis, -1, sizeof dis);
    cin >> A >> B >> C;
    bfs();
    if (flag)
        cout << "impossible";
}

signed main()
{
    int t = 1;
    // cin>>t;
    while (t--)
    {
        solve();
    }
    return 0;
}

//感谢学长的讲解 hwh ;

~~~//仅当笔者个人备忘录使用。


http://www.niftyadmin.cn/n/5478442.html

相关文章

汽车传动轴原理?

汽车的传动轴&#xff08;Drive Shaft&#xff09;是传递发动机动力到车辆驱动轮的关键部件之一&#xff0c;它的原理和作用如下&#xff1a; 传递动力&#xff1a; 传动轴负责将发动机产生的动力传递到车辆的驱动轮&#xff0c;驱动车辆行驶。传动轴通常连接在发动机和差速器之…

Python从0到100(十一):Python字典介绍及运用

前言&#xff1a; 零基础学Python&#xff1a;Python从0到100最新最全教程。 想做这件事情很久了&#xff0c;这次我更新了自己所写过的所有博客&#xff0c;汇集成了Python从0到100&#xff0c;共一百节课&#xff0c;帮助大家一个月时间里从零基础到学习Python基础语法、Pyth…

LangChain:大型语言模型(LLMs)-- ChatGLM

1. 介绍 LangChain 是一个领先的框架&#xff0c;用于构建由大型语言模型&#xff08;LLM&#xff09;驱动的应用程序。在这个框架内&#xff0c;ChatGLM 作为一个重要的组件&#xff0c;为用户提供了强大的双语&#xff08;中文-英文&#xff09;对话功能。ChatGLM 基于通用的…

【三十六】【算法分析与设计】综合练习(3),39. 组合总和,784. 字母大小写全排列,526. 优美的排列

目录 39. 组合总和 对每一个位置进行枚举 枚举每一个数出现的次数 784. 字母大小写全排列 526. 优美的排列 结尾 39. 组合总和 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target &#xff0c;找出 candidates 中可以使数字和为目标数 target 的 所有 不…

深入理解JVM后端优化技术-方法内联

相关系列 深入理解JVM后端优化技术-逃逸分析(Escape Analysis)-CSDN博客 深入理解JVM后端优化技术-锁消除&#xff08;Lock Elision)-CSDN博客 深入理解JVM后端优化技术-锁粗化(Lock Coarsening)-CSDN博客 jvm只是负责依次将字节码指令逐次转换成机器码。而在转换过程中&#x…

【Redis】Redis群集的三种模式(主从、哨兵、群集)

redis群集有三种模式&#xff0c;分别是主从同步/复制、哨兵模式、Cluster&#xff0c;下面会讲解一下三种模式的工作方式&#xff0c;以及如何搭建cluster群集 ●主从复制&#xff1a;主从复制是高可用Redis的基础&#xff0c;哨兵和集群都是在主从复制基础上实现高可用的。主…

【js】监听文件上传下载进度,设置请求头信息与获取响应头信息

监听文件上传下载进度 例子&#xff1a;html部分 <input type"file" id"selectFile"> <span id"progress1"></span><button id"downloadFile">download</button> <span id"progress2"&g…

详解cmake简单语法与使用

注意&#xff1a;这是一篇cmake入门浅显的文章&#xff0c;深入学习的话没必要阅读。 CMake的使用流程及其语法非常丰富&#xff08;其实就是过于灵活&#xff0c;一个项目一个风格&#xff0c;看上去相当麻烦&#xff09;&#xff0c;下面逐步介绍一些核心概念和常用命令&…