找机厅 洛谷 BFS

P10234 [yLCPC2024] B. 找机厅 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
#include<bits/stdc++.h>
#define pii pair<int,int>
#define fr first
#define sc second
using namespace std;
string maze[2000];
int vis[2000][2000];
char dirs[2005][2005];
string s="URDL";
int n,m;
int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
pii parent[2000][2000];
bool check(int x,int y)
{return x>=0&&x<n&&y>=0&&y<m;
}
bool bfs(int x,int y)
{for(int i=0;i<n;i++)for(int j=0;j<m;j++){vis[i][j]=0;parent[i][j]={-1,-1};dirs[i][j]=' ';}queue<pii>q;q.push({0,0});vis[0][0]=1;while(!q.empty()){pii now=q.front();if(now.fr==n-1&&now.sc==m-1)return true;q.pop();for(int i=0;i<4;i++){int nx,ny;nx=now.first+dir[i][0];ny=now.second+dir[i][1];if(check(nx,ny)&&!vis[nx][ny]){if(maze[nx][ny]==maze[now.fr][now.sc])continue;q.push({nx,ny});vis[nx][ny]=vis[now.fr][now.sc]+1;parent[nx][ny]=now;dirs[nx][ny]=s[i];}}}return false;
}
void dfs(int x,int y)
{if(!x&&!y)return;dfs(parent[x][y].fr,parent[x][y].sc);cout<<dirs[x][y];
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t;cin>>t;while(t--){cin>>n>>m;for(int i=0;i<n;i++)cin>>maze[i];if(bfs(0,0)){cout<<vis[n-1][m-1]-1<<'\n';dfs(n-1,m-1);cout<<'\n';}else cout<<"-1\n";}return 0;
}
刚开始我是没想到怎么打印出路径的,但是题解几乎搜不到,所以只能问了文心一言,结果她终于有用了一回,她让我弄个数组记录父节点,再弄个数组记录路径,然后直接DFS。跟着改了下,结果没想到真的AC了。
不开新的数组也可以,从最后的节点开始再来一次BFS,然后把路径存起来再反向输出,我试试。
是可以的,再用一遍bfs。但是代码比存父节点再用dfs稍微长一点,但是这些东西都是一样的。
#include<bits/stdc++.h>
#define pii pair<int,int>
#define fr first
#define sc second
using namespace std;
string mz[2000];
int vis[2000][2000];
string s="DLUR";
int n,m;
int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
bool check(int x,int y)
{return x>=0&&x<n&&y>=0&&y<m;
}
bool bfs(int x,int y)
{for(int i=0;i<n;i++)for(int j=0;j<m;j++)vis[i][j]=0;queue<pii>q;q.push({0,0});vis[0][0]=1;while(!q.empty()){pii now=q.front();if(now.fr==n-1&&now.sc==m-1)return true;q.pop();for(int i=0;i<4;i++){int nx,ny;nx=now.first+dir[i][0];ny=now.second+dir[i][1];if(check(nx,ny)&&!vis[nx][ny]){if(mz[nx][ny]==mz[now.fr][now.sc])continue;q.push({nx,ny});vis[nx][ny]=vis[now.fr][now.sc]+1;}}}return false;
}
void sfb(int x,int y)
{string ans;queue<pii>q;q.push({x,y});while(!q.empty()){pii now=q.front();q.pop();for(int i=0;i<4;i++){int nx,ny;nx=now.fr+dir[i][0];ny=now.sc+dir[i][1];if(check(nx,ny)&&mz[nx][ny]!=mz[now.fr][now.sc]){if(vis[nx][ny]==vis[now.fr][now.sc]-1){ans+=s[i];q.push({nx,ny});break;}}}}reverse(ans.begin(),ans.end());cout<<ans<<'\n';
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t;cin>>t;while(t--){cin>>n>>m;for(int i=0;i<n;i++)cin>>mz[i];if(bfs(0,0)){cout<<vis[n-1][m-1]-1<<'\n';sfb(n-1,m-1);cout<<'\n';}else cout<<"-1\n";}return 0;
}
加油,嘻嘻。感觉这题还算简单的。
相关文章:
找机厅 洛谷 BFS
P10234 [yLCPC2024] B. 找机厅 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) #include<bits/stdc.h> #define pii pair<int,int> #define fr first #define sc second using namespace std; string maze[2000]; int vis[2000][2000]; char dirs[2005][2005]; st…...
软件无线电系列——模拟无线电、数字无线电、软件无线电
本节目录 一、模拟无线电 二、数字无线电 1、窄带数字无线电 2、宽带数字无线电 三、软件无线电本节内容 一、模拟无线电 20世纪80年代的模拟体制(美国的AMPS/欧洲的TACS)被称为第一代移动通信,简称1G,主要目标是为在大范围内有限的用户提供移动电话服务。最主要的…...
XSS_lab(level11-level18)
level11: 还是url这里,输入:<script>alert(1)</script> 与上一题相似 构建:?t_link1&t_history2&t_sort3&t_ref4 我们发现t_sort是可用的 构建:?t_sort1" type"button" οnclickalert(1) // 把双引号过滤了 这里无法使用实体编码…...
【git】常用操作
基础操作 git init 初始化仓库 要使用 Git 进行版本管理,必须先初始化仓库, 执行了 git init命令的目录下就会生成 .git 目录。这个 .git 目录里存储着管理当前目录内容所需的仓库数据 git status 查看仓库状态 工作树和仓库在被操作的过程中࿰…...
蓝桥杯第十一届电子类单片机组程序设计
目录 前言 单片机资源数据包_2023(点击下载) 一、第十一届比赛原题 1.比赛题目 2.赛题解读 1)计数功能 2)连续按下无效按键 二、部分功能实现 1.计数功能的实现 2.连续按下无效按键的处理 3.其他处理 1)对于…...
Java中文乱码问题解析与解决方案
在日常工作中,我们经常会遇到中文乱码的问题。乱码问题不仅影响用户体验,还可能导致数据丢失或解析错误。因此,了解和掌握中文乱码问题的原因和解决方案,对于Java开发者来说至关重要。本文将分析常见的Java中文乱码场景࿰…...
AIGC笔记--Maya提取和修改FBX动作文件
目录 1--Maya数据解析 2--FBX SDK导出6D数据 3--6D数据映射和Maya可视化 完整项目代码:Data-Processing/FBX_SDK_Maya 1--Maya数据解析 在软件Maya中直接拖入FBX文件,可以播放和查看人体各个骨骼关节点的数据: 对于上图来说,…...
【刷题训练】LeetCode125. 验证回文串
验证回文串 题目要求 示例 1: 输入: s “A man, a plan, a canal: Panama” 输出:true 解释:“amanaplanacanalpanama” 是回文串。 示例 2: 输入:s “race a car” 输出:false 解释:“rac…...
optee默认安全配置
OP-TEE(Open Portable Trusted Execution Environment)是一个开源的可移植的可信执行环境(TEE),用于提供安全和受保护的执行环境。它旨在为基于 ARM 架构的设备提供强大的安全性和隔离能力。 OP-TEE 主要由两部分组成…...
Arcgis新建位置分配求解最佳商店位置
背景 借用Arcgis帮助文档中的说明:在本练习中,您将为连锁零售店选择可以获得最大业务量的商店位置。主要目标是要将商店定位在人口集中地区附近,因为这种区域对商店的需求量较大。设立这一目标的前提是假设人们往往更多光顾附近的商店,而对于距离较远的商店则较少光顾。您…...
【C++初阶】C++入门(上)
C的认识 ①什么是C? C语言是结构化和模块化的语言,适合处理较小规模的程序。对于复杂的问题,规模较大的程序,需要高度的抽象和建模时,C语言则不合适。 于是1982年,Bjarne Stroustrup(本…...
Vue.js+SpringBoot开发校园疫情防控管理系统
目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 学生2.2 老师2.3 学校管理部门 三、系统展示四、核心代码4.1 新增健康情况上报4.2 查询健康咨询4.3 新增离返校申请4.4 查询防疫物资4.5 查询防控宣传数据 五、免责说明 一、摘要 1.1 项目介绍 基于JAVAVueSpringBoot…...
客服销冠偷偷用的提效神器!无广很实用
近期发现我的同事每天上班必登录的一款软件——客服宝聊天助手,用过才发现:真客服办公的提效神器!感兴趣的小伙伴请往下看~一、客服宝的简介:客服宝聊天助手,是一款跨平台快捷回复工具。自带多种功能,有效帮…...
蓝桥杯刷题|02入门真题
[蓝桥杯 2022 省 B] 刷题统计 题目描述 小明决定从下周一开始努力刷题准备蓝桥杯竞赛。他计划周一至周五每天做 a 道题目,周六和周日每天做 b 道题目。请你帮小明计算,按照计划他将在第几天实现做题数大于等于 n 题? 输入格式 输入一行包含三个整数…...
Jenkins cron定时构建触发器
from: https://www.jenkins.io/doc/book/pipeline/syntax/#cron-syntax 以下内容为根据Jenkins官方文档cron表达式部分翻译过来,使用机翻加个人理解补充内容,包括举例。 目录 介绍举例:设置方法方法一:方法二…...
【编程向导】JavaScript-创建对象一期讲解
工厂模式 工厂模式 是用来创建对象的一种最常用的设计模式。工厂模式不暴露创建对象的具体逻辑,而是将逻辑封装在一个函数中,那么这个函数就可以被视为一个工厂。工厂模式常见于大型项目,例如 jQuery 的 $ 对象,我们创建选择器对…...
【MySQL性能优化】- 一文了解MVCC机制
MySQL理解MVCC 😄生命不息,写作不止 🔥 继续踏上学习之路,学之分享笔记 👊 总有一天我也能像各位大佬一样 🏆 博客首页 怒放吧德德 To记录领地 🌝分享学习心得,欢迎指正ÿ…...
性能测试-Redis
一、测试注意点 1、缓存预热 如果程序初次运行,此时由于数据尚未加载到缓存,则程序的响应时间会明显变长 注意事项: 性能测试的时候 出现 非常不稳定的现象程序刚启动,它的性能 明显 低于 已经运行一段时间的 1.1 测试缓存没…...
浅析C++的指针与引用
浅析C的指针与引用 文章目录 浅析C的指针与引用一、对比引用与指针二、引用左值引用右值引用引用折叠 三、指针与引用的性能差距总结 一、对比引用与指针 总论: 引用指针必须初始化可以不初始化不能为空可以为空不能更换目标可以更换目标 引用必须初始化ÿ…...
【消息队列开发】 实现消息删除逻辑
文章目录 🍃前言🌲实现步骤🚩检验参数的合法性🚩读取Message数据🚩二进制转为message🚩isValid 设置为无效🚩写入文件🚩更新统计文件🚩特别注意🚩完整代码 ⭕…...
Vim 调用外部命令学习笔记
Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...
【Python】 -- 趣味代码 - 小恐龙游戏
文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...
智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql
智慧工地管理云平台系统,智慧工地全套源码,java版智慧工地源码,支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求,提供“平台网络终端”的整体解决方案,提供劳务管理、视频管理、智能监测、绿色施工、安全管…...
将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?
Otsu 是一种自动阈值化方法,用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理,能够自动确定一个阈值,将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...
从零实现STL哈希容器:unordered_map/unordered_set封装详解
本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说,直接开始吧! 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...
css的定位(position)详解:相对定位 绝对定位 固定定位
在 CSS 中,元素的定位通过 position 属性控制,共有 5 种定位模式:static(静态定位)、relative(相对定位)、absolute(绝对定位)、fixed(固定定位)和…...
.Net Framework 4/C# 关键字(非常用,持续更新...)
一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...
uniapp手机号一键登录保姆级教程(包含前端和后端)
目录 前置条件创建uniapp项目并关联uniClound云空间开启一键登录模块并开通一键登录服务编写云函数并上传部署获取手机号流程(第一种) 前端直接调用云函数获取手机号(第三种)后台调用云函数获取手机号 错误码常见问题 前置条件 手机安装有sim卡手机开启…...
Python 实现 Web 静态服务器(HTTP 协议)
目录 一、在本地启动 HTTP 服务器1. Windows 下安装 node.js1)下载安装包2)配置环境变量3)安装镜像4)node.js 的常用命令 2. 安装 http-server 服务3. 使用 http-server 开启服务1)使用 http-server2)详解 …...
从面试角度回答Android中ContentProvider启动原理
Android中ContentProvider原理的面试角度解析,分为已启动和未启动两种场景: 一、ContentProvider已启动的情况 1. 核心流程 触发条件:当其他组件(如Activity、Service)通过ContentR…...
