学习总结2

解题思路

用bfs进行搜索,标记A罐B罐所保存的水的出现情况,当再次出现的时候停止搜索,然后用数组模拟链表进行保存路径.最后输出.

代码

#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
using namespace std;
int g[120][120];
struct s
{int x;int y;
}d[120*120];
int l,r;
struct ss
{int x;int y;int z;
}j[120][120];
int a,b,c;
int k,i;
int bfs()
{int tx,ty,z;while(l<r){for(z=0;z<6;z++){tx=d[l].x;ty=d[l].y;switch(z){case 0:tx=a;break;case 1:ty=b;break;case 2:tx=0;break;case 3:ty=0;break;case 4:if(tx!=0){if(tx+ty<=b){ty=tx+ty;tx=0;}else{tx=tx-(b-ty);ty=b;}}break;case 5:if(ty!=0){if(tx+ty<=a){tx=ty+tx;ty=0;}else{ty=ty-(a-tx);tx=a;}}break;}if(tx>a||ty>b||tx<0||ty<0)continue;if(tx==c||ty==c){k=tx;i=ty;j[k][i].x=d[l].x;j[k][i].y=d[l].y;j[k][i].z=z;g[tx][ty]=g[d[l].x][d[l].y]+1;return 0;}if(g[tx][ty]==-1){g[tx][ty]=g[d[l].x][d[l].y]+1;d[r].x=tx;d[r++].y=ty;j[tx][ty].x=d[l].x;j[tx][ty].y=d[l].y;j[tx][ty].z=z;}}l++;}return 0;
}void print(int x,int y)
{if(x==0&&y==0)return ;print(j[x][y].x,j[x][y].y);switch(j[x][y].z){case 0:printf("FILL(1)\n");break;case 1:printf("FILL(2)\n");break;case 2:printf("DROP(1)\n");break;case 3:printf("DROP(2)\n");break;case 4:printf("POUR(1,2)\n");break;case 5:printf("POUR(2,1)\n");break;}return ;
}int main()
{scanf("%d%d%d",&a,&b,&c);d[r].x=0;d[r++].y=0;memset(g,-1,sizeof(int )*120*120);g[0][0]=0;bfs();if(k==0&&i==0){printf("impossible\n");}else{printf("%d\n",g[k][i]);print(k,i);}return 0;
}

解题思路

这道题用bfs就行了.以两个人为起点对全图进行搜索,用一个数组保存到每一个地方所用的最短的步数.最后比较两人到所有的kfc所用的步数的总和输出最小的就行了.

代码

#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
using namespace std;
char g[210][210];
int j[210][210];
int j2[210][210];
int ne[5][2]={{1,0},{-1,0},{0,1},{0,-1}};
int n,m;
struct di
{int x;int y;
}sy,sm,kfc[210*210],dl[210*210];
int l,r;
int k;
int sum;int bfs()
{int tx,ty,z;while(l<r){for(z=0;z<4;z++){tx=ne[z][0]+dl[l].x;ty=ne[z][1]+dl[l].y;if(tx<0||tx>n||ty<0||ty>m)continue;if(g[tx][ty]!='#'&&j[tx][ty]==0){j[tx][ty]=j[dl[l].x][dl[l].y]+1;dl[r].x=tx;dl[r++].y=ty;}}l++;}return 0;
}int bfs2()
{int tx,ty,z;while(l<r){for(z=0;z<4;z++){tx=ne[z][0]+dl[l].x;ty=ne[z][1]+dl[l].y;if(tx<0||tx>n||ty<0||ty>m)continue;if(g[tx][ty]!='#'&&j2[tx][ty]==0){j2[tx][ty]=j2[dl[l].x][dl[l].y]+1;dl[r].x=tx;dl[r++].y=ty;}}l++;}return 0;
}int main()
{int x,y,s;while(~scanf("%d%d",&n,&m)){sum=9999999;k=0;for(x=0;x<n;x++){scanf("%s",g[x]);}for(x=0;x<n;x++){for(y=0;y<m;y++){if(g[x][y]=='Y'){sy.x=x;sy.y=y;}if(g[x][y]=='M'){sm.x=x;sm.y=y;}if(g[x][y]=='@'){kfc[k].x=x;kfc[k++].y=y;}}}memset(j,0,sizeof(int)*210*210);l=0;r=0;dl[r].x=sy.x;dl[r++].y=sy.y;bfs();memset(j2,0,sizeof(int)*210*210);l=0;r=0;dl[r].x=sm.x;dl[r++].y=sm.y;bfs2();for(x=0;x<k;x++){if(j[kfc[x].x][kfc[x].y]!=0&&j2[kfc[x].x][kfc[x].y]!=0)if((j[kfc[x].x][kfc[x].y]+j2[kfc[x].x][kfc[x].y])<sum)sum=j[kfc[x].x][kfc[x].y]+j2[kfc[x].x][kfc[x].y];}printf("%d\n",sum*11);}return 0;
}

解题思路

用bfs搜索,要注意的是地图是三维的,传送到下一层之后可能的情况(直接见到公主,撞死,进入另一个传送门).

代码

#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
using namespace std;
char g[3][15][15];
int j[3][15][15];
struct ss
{int x;int y;int z;
}d[15*15*3];
int ne[5][2]={{1,0},{-1,0},{0,1},{0,-1}};
int l,r;
int n,m,t;
int bfs()
{int z,tx,ty,tz;while(l<r){for(int z=0;z<4;z++){tx=d[l].x+ne[z][0];ty=d[l].y+ne[z][1];tz=d[l].z;if(tx<0||ty<0||tx>=n||ty>=m)continue;if(g[tz][tx][ty]=='P'){return j[tz][tx][ty]=j[d[l].z][d[l].x][d[l].y]+1;}if(g[tz][tx][ty]!='*'&&j[tz][tx][ty]==-1){j[tz][tx][ty]=j[d[l].z][d[l].x][d[l].y]+1;if(g[tz][tx][ty]=='#'){if(tz==0){tz++;}else{tz--;}if(g[tz][tx][ty]=='#'||j[tz][tx][ty]!=-1){if(tz==0){tz++;}else{tz--;}continue;}if(g[tz][tx][ty]=='*'||j[tz][tx][ty]!=-1){if(tz==0){tz++;}else{tz--;}continue;}if(g[tz][tx][ty]=='P'){return j[tz][tx][ty]=j[d[l].z][d[l].x][d[l].y]+1;}j[tz][tx][ty]=j[d[l].z][d[l].x][d[l].y]+1;}d[r].x=tx;d[r].y=ty;d[r++].z=tz;}}l++;}return 999999;
}
int main()
{int k;scanf("%d",&k);for(int z=0;z<k;z++){memset(j,-1,sizeof(int )*3*15*15);l=r=0;scanf("%d%d%d",&n,&m,&t);for(int x=0;x<n;x++){scanf("%s",g[0][x]);}getchar();for(int x=0;x<n;x++){scanf("%s",g[1][x]);}d[r].x=0;d[r].y=0;d[r++].z=0;j[0][0][0]=0;int sum=bfs();if(sum<=t){printf("YES\n");}else{printf("NO\n");}}return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/282731.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Python学习day3

知识&#xff1a; #继承&#xff0c;创建有继承的类 #父类、子类 #class 子类(父类): #调用时找父类的构造函数&#xff0c;如果子类自己有某函数则调用子类的&#xff0c;否则调用父类的 #在子类有构造函数的时候调用父类&#xff0c;可以用super().__init__的方法调用父类函数…

基于springboot的“漫画之家”系统

目录 背景 技术简介 系统简介 界面浏览 背景 随着科技的不断进步&#xff0c;计算机已经变成了人们日常生活和工作不可或缺的工具。在这样的环境下&#xff0c;互联网技术被广泛运用于各个领域&#xff0c;以提升工作和生活的效率&#xff0c;推动了网络信息技术的迅猛发展…

基于Springboot的西安旅游系统(有报告)。Javaee项目,springboot项目。

演示视频&#xff1a; 基于Springboot的西安旅游系统&#xff08;有报告&#xff09;。Javaee项目&#xff0c;springboot项目。 项目介绍&#xff1a; 采用M&#xff08;model&#xff09;V&#xff08;view&#xff09;C&#xff08;controller&#xff09;三层体系结构&…

力扣热门算法题 52. N 皇后 II,53. 最大子数组和,54. 螺旋矩阵

52. N 皇后 II&#xff0c;53. 最大子数组和&#xff0c;54. 螺旋矩阵&#xff0c;每题做详细思路梳理&#xff0c;配套Python&Java双语代码&#xff0c; 2024.03.20 可通过leetcode所有测试用例。 目录 52. N 皇后 II 解题思路 完整代码 Python Java 53. 最大子数组…

多线程基础 -概念、创建、等待、分离、终止

文章目录 一、 线程概念1. 什么是线程2. 线程的优点3.线程的缺点4. 线程异常5. 线程用途 二、 Linux进程VS线程1. 进程和线程2. 进程和线程的地址空间3. 进程和线程的关系 三、Linux线程控制1. POSIX线程库2. 线程创建3. 线程ID及进程地址空间布局4. 线程终止5. 线程等待6. 线程…

Linux初识环境变量

&#x1f30e;环境变量【上】 文章目录&#xff1a; 环境变量 什么是环境变量 关于命令行参数 环境变量       简单了解       为什么需要环境变量       系统中其他环境变量 总结 前言&#xff1a; 环境变量是一种非常重要的概念&#xff0c;它们对于系统的…

长安链正式发布三周年,技术更迭支撑产业变革

导语&#xff1a; 2024年1月27日长安链正式发布三周年&#xff0c;开源社区借开年之际与大家一同回顾长安链三年来的技术发展历程&#xff0c;每一个里程碑的建设都得益于与长安链同行的合作伙伴与开发者&#xff0c;希望在2024年可以共同携手继往开来&#xff0c;为数字经济发…

Mysql面试题以及答案

1 基础 1.1、MySQL有哪些数据库类型&#xff1f; 数值类型 有包括 TINYINT、SMALLINT、MEDIUMINT、INT、BIGINT&#xff0c;分别表示 1 字节、2 字节、3 字节、4 字节、8 字节的整数类型。 1&#xff09;任何整数类型都可以加上 UNSIGNED 属性&#xff0c;表示无符号整数。 …

Matlab快捷键与函数

注释&#xff1a;注释对于代码的重要性我们就不做过多的解释了。不做注释的代码不是好代码。选中要注释的语句&#xff0c;按快捷键CtrlR,或者在命令行窗口上面的注释地方可以进行注释。当然也可以直接在语句前面“%”就可以&#xff08;注意&#xff1a;一定要用英文符号&…

第十二届蓝桥杯省赛CC++ 研究生组

十二届省赛题 第十二届蓝桥杯省赛C&C 研究生组-卡片 第十二届蓝桥杯省赛C&C 研究生组-直线 第十二届蓝桥杯省赛C&C 研究生组-货物摆放 第十二届蓝桥杯省赛C&C 研究生组-路径 第十二届蓝桥杯省赛C&C 研究生组-时间显示 第十二届蓝桥杯省赛C&C 研究生组…

石油炼化5G智能制造工厂数字孪生可视化平台,推进行业数字化转型

石油炼化5G智能制造工厂数字孪生可视化平台&#xff0c;推进行业数字化转型。在石油炼化行业&#xff0c;5G智能制造工厂数字孪生可视化平台的出现&#xff0c;为行业的数字化转型注入了新的活力。石油炼化行业作为传统工业的重要领域&#xff0c;面临着资源紧张、环境压力、安…

Matlab 双目相机标定(内置函数)

文章目录 一、简介二、实现代码三、实现效果参考资料一、简介 相机标定的目的就是要找到从世界坐标转换为图像坐标所用到的投影P矩阵各个系数(即相机的内参与外参)。具体过程如下所述: 1、首先我们需要获取一个已知图形的图像(这里我们使用MATLAB所提供的数据)。 2、找到同…

_nodemon自动重启服务器

文章目录 1.安装模块 nodemon1.1安装方式2.jason文件里面可以存储自定义指令 由于每次修改代码都要重启服务器&#xff0c;所以我们希望有一种方式自动监视代码修改&#xff0c;自动启动服务器nodemon模块解决了这个问题 1.安装模块 nodemon 1.1安装方式 全局安装 npm i node…

计算地球圆盘负荷产生的位移

1.研究背景 计算受表面载荷影响的弹性体变形问题有着悠久的历史&#xff0c;涉及到许多著名的数学家和物理学家&#xff08;Boussinesq 1885&#xff1b;Lamb 1901&#xff1b;Love 1911&#xff0c;1929&#xff1b;Shida 1912&#xff1b;Terazawa 1916&#xff1b;Munk &…

TCP | TCP协议格式 | 三次握手

1.TCP协议 为什么需要 TCP 协议 &#xff1f;TCP 工作在哪一层&#xff1f; IP网络层是不可靠的&#xff0c;TCP工作在传输层&#xff0c;保证数据传输的可靠性。 TCP全称为 “传输控制协议&#xff08;Transmission Control Protocol”&#xff09;。 TCP 是面向连接的、可靠…

京东云开发者:DDD 学习与感悟 —— 向屎山冲锋

原文地址:https://mp.weixin.qq.com/s/Hvq1ttBopbxypatVcKcLiA 软件系统是通过软件开发来解决某一个业务领域或问题单元而产生的一个交付物。而通过软件设计可以帮助我们开发出更加健壮的软件系统。因此&#xff0c;软件设计是从业务领域到软件开发之间的桥梁。而DDD是软件设计…

opengl 学习(六)-----坐标系统与摄像机

坐标系统与摄像机 分类引言坐标系统摄像机教程在CMake中使用全局定义预编译宏,来控制是否开启错误检查补充 分类 opengl c 引言 OpenGL希望在每次顶点着色器运行后&#xff0c;我们可见的所有顶点都为标准化设备坐标(Normalized Device Coordinate, NDC)。也就是说&#xff…

OCP NVME SSD规范解读-14.Firmware固件升级要求

4.11节 Firmware Update Requirements 描述了数据中心NVMe SSD固件更新的具体要求&#xff0c;确保固件升级过程既安全又可靠&#xff0c;同时充分考虑了设备在升级过程中的可用性和功能性。 FWUP-1: 设备必须记录每一次固件激活过程。这意味着固件升级过程中&#xff0c;设备会…

【Dynamics 365 FO】在Dynamics 365中建立一个SSRS报表

建立一个SSRS报表主要有以下8个步骤&#xff1a; 目录 1、新建合约类 合约类&#xff08;Contract Class&#xff09;的作用是获取查询数据源所需要的数据&#xff0c;在我们点开报表的时候&#xff0c;系统会弹出一个对话框让我们来选择字段来筛选要查询数据&#xff0c;合…

基于Java的厦门旅游电子商务预订系统(Vue.js+SpringBoot)

目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 景点类型模块2.2 景点档案模块2.3 酒店管理模块2.4 美食管理模块 三、系统设计3.1 用例设计3.2 数据库设计3.2.1 学生表3.2.2 学生表3.2.3 学生表3.2.4 学生表 四、系统展示五、核心代码5.1 新增景点类型5.2 查询推荐的…