BFS专题7 多终点迷宫问题
题目:
样例:
|
|

思路:
单纯的 BFS 迷宫问题,只是标记一下每个点的 step,注意初始化答案数组都为 -1.
代码详解如下:
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <unordered_map>
#define endl '\n'
#define x first
#define y second
#define mk make_pair
#define YES puts("YES")
#define NO puts("NO")
#define umap unordered_map
#define All(x) x.begin(),x.end()
#pragma GCC optimize(3,"Ofast","inline")
#define ___G std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
using namespace std;// 坐标
using PII = pair<int,int>;const int N = 500;// 地图
int n,m;
int g[N][N];// 答案步数数组
int ans[N][N];// 标记走动的坐标
bool st[N][N];// 控制方向坐标
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};// 坐标走动条件
inline bool isRun(int &x,int &y)
{return (~x && ~y && x < n && y < m && !g[x][y] && !st[x][y]);
}inline void BFS()
{int step = 0;queue<PII>q;// 存储起点q.push(mk(0,0));// 开始BFSwhile(q.size()){int sz = q.size();while(sz--){auto now = q.front();q.pop();// 标记答案步数数组ans[now.x][now.y] = step;// 标记当前走动的坐标st[now.x][now.y] = true;// 开始寻找走动方向的坐标for(int i = 0;i < 4;++i){int bx = now.x + dx[i];int by = now.y + dy[i];// 如果可以走动该方向if(isRun(bx,by)){// 标记并存储st[bx][by] = true;q.push(mk(bx,by));}}}++step;}
}// 输出答案步数数组
inline void PrintAns()
{for(int i = 0;i < n;++i){for(int j = 0;j < m;++j){if(j) cout << ' ';cout << ans[i][j];}if(i < n) cout << endl;}
}inline void solve()
{cin >> n >> m;for(int i = 0;i < n;++i){for(int j = 0;j < m;++j){cin >> g[i][j];// 答案数组初始化ans[i][j] = -1;}}// 开始BFSBFS();// 输出答案PrintAns();
}int main()
{
// freopen("a.txt", "r", stdin);___G;int _t = 1;
// cin >> _t;while (_t--){solve();}return 0;
}
最后提交:
相关文章:
BFS专题7 多终点迷宫问题
题目: 样例: 输入 3 3 0 0 0 1 0 0 0 1 0 输出 0 1 2 -1 2 3 -1 -1 4 思路: 单纯的 BFS 迷宫问题,只是标记一下每个点的 step,注意初始化答案数组都为 -1. 代码详解如下: #include <iostream> #…...
ES6中对象新增了哪些扩展?
一、属性的简写 当对象字面量的属性名与变量名相同时,可以省略属性名,直接使用变量名作为属性名。 const x 10; const y 20;// ES6之前 const obj1 { x: x, y: y };// ES6属性简写 const obj2 { x, y };注意:简写的对象方法不能用作构造…...
蓝桥杯每日一题2023.9.22
4960. 子串简写 - AcWing题库 题目描述 题目分析 原本为纯暴力但是发现会超时,可以加入前缀和,从前往后先记录一下每个位置c1出现的次数 再从前往后扫一遍,如果遇到c2就将答案加上此位置前的所有c1的个数(直接加上此位置的前缀…...
vscode左键无法跳转到定义的文件
之前用vscode的时候,明明是可以ctrl键鼠标左键跳转到定义文件的,突然之间就不行了,鼠标移到引入上根本都没有下划线,无法跳转 解决方法: 项目的根目录新建 jsconfig.json 文件,代码如下 {"compiler…...
c、c++排序的相关知识(归并排序、计数排序、稳定性等)
排序,是对给定的一组数,按照某种逻辑关系,进行位置上的移动。由于排序至少需要将所有数过一遍(正常情况下,非特殊数组),因此排序的时间复杂度一定不能小于O(N)。 归并排…...
oracle定时任务的使用
常见错误: PLS-00225: subprogram or cursor xxx reference is out of scope # job名字太长PLS-00201: identifier COUNT_JOB.SUBMIT must be declared # DBMS_JOB.SUBMIT是固定写法创建存储过程 -- 建表 CREATE TABLE TEST_A(TEST_ADD_DATA DATE); -- 存储过程 C…...
VSCode 配置 Lua 开发环境(清晰明了)
概述 由于 AutoJS 学得已经差不多了,基本都会了,现在开始向其他游戏脚本框架进发, Lua 语言很强大,就不多说, 按键精灵、触动精灵等等都是用该语言编程脚本的,由于按键精灵、触动精灵 和 AutoJS 类似,不是…...
JS合并2个远程pdf
要在HTML和JavaScript中读取远程PDF文件的矢量数据并合并两个PDF文件,您可以使用pdf-lib和Axios库。以下是使用pdf-lib和Axios在HTML和JavaScript中读取和合并远程PDF文件的步骤: 1. 引入 首先,确保您在HTML文件中引入了pdf-lib和Axios库。…...
TikTok的伦理挑战:虚拟世界与现实世界的交汇
在数字时代,社交媒体平台已经不再只是一个信息传播的工具,它已经深刻地改变了我们的社交行为、价值观和伦理观。 而在这一领域的佼佼者之一,TikTok,正面临着伦理挑战,这是虚拟世界与现实世界交汇的产物。 本文将深入…...
C# 获取磁盘空间大小的方法
方法一:利用System.IO.DriveInfo.GetDrives方法来获取 /// 获取指定驱动器的空间总大小(单位为B)////// 只需输入代表驱动器的字母即可 (大写)///public static long GetHardDiskSpace(string str_HardDiskName){long totalSize new long();…...
JVM机制理解与调优方案
作者:逍遥Sean 简介:一个主修Java的Web网站\游戏服务器后端开发者 主页:https://blog.csdn.net/Ureliable 觉得博主文章不错的话,可以三连支持一下~ 如有需要我的支持,请私信或评论留言! 前言 很多Java开发…...
Django的设计模式及模板层
Django的设计模式及模板层 设计模式MVC和MVT MVC 代表 Model-View-Controller(模型-视图-控制器)模式。 M 模型层(Model),主要用于对数据库层的封装 V 视图层(View),用于向用户展示结果 (WHAT HOW) C 控制(Controller,用于处理请求、获取数据、返回结果(重要) 作…...
写代码生成流程图
我们在写文档,博客的时候,一般都会使用markdown语法,最常见的就是一些github开源项目的README。有时候会去画一些流程图,例如使用process.on或者xmind等第三方网站,然后截图插入到文档中。 今天我们介绍一种使用代码直…...
python reportlab生成pdf
这里自定义了pagetemplate,使用BaseDocTemplate,但我感觉一般使用SimpleDocTemplate就可以。 from reportlab.platypus import Frame from reportlab.lib.pagesizes import A4, landscapepadding dict(leftPadding72,rightPadding72,topPadding72,bott…...
第一次作业题解
第一次作业题解 P5717 【深基3.习8】三角形分类 思路 考的是if()的使用,还要给三条边判断大小 判断优先级: 三角形?直角、钝角、锐角等腰等边 判断按题给顺序来 代码 #include <stdio.h> int main() {int a 0, b 0, c 0, x 0, y 0, z 0…...
美篇作文网教学资源源码-自带作文数据
非常漂亮的UI设计和页面排版! 自适应手机pc端 页面内容均支持自定义 可以用来做网站矩阵,或者增强你其他网站板块,或者单独运营都可以。 可以通过广告方式变现,或者引流等等 友好的seo,更容易被浏览器收录 关注青狐…...
电脑软件:Duplicate Cleaner Pro 5.16 重复文件清理软件(附下载)
大家平时在使用电脑的时候,会经常从网上下载文件或者从其他电脑拷贝文件到自己的电脑上。久而久之就会在电脑中存放很多相同的文件,并且会越积越多,不仅占用很多磁盘空间,在文件管理上也非常混乱不方便。如何解决呢? …...
支持笔记本电脑直插直充,TOWE 65W智能快充PDU超级插座
电源插排在我们的生活中是必不可少的电器配件。今天,我们日常生活中所使用的电子设备越来越多,无论是手机、平板、笔记本电脑还是各种家用电器,都需要电源来驱动。虽然相对于其他电器来说,插排结构比较简单,但现代家庭…...
部署Kafka
kafka:kafka_2.13-3.5.1 NOTE: Your local environment must have Java 8 installed. Apache Kafka can be started using ZooKeeper or KRaft. To get started with either configuration follow one the sections below but not both. 1 Windows单机 1.1 Kafka w…...
Open3D 进阶(11)使用GMM-Tree算法对点云配准
GMM-Tree算法 一、算法原理1、主要函数2、参考文献二、代码实现三、结果展示1、点云初始位置2、配准后的位置四、测试数据本文由CSDN点云侠原创,原文链接。如果你不是在点云侠的博客中看到该文章,那么此处便是不要脸的爬虫。 一、算法原理 1、...
SRS + FFmpeg WebRTC 循环推流环境搭建
SRS FFmpeg WebRTC 循环推流环境搭建指南 本指南介绍如何使用 Docker Compose 快速搭建一个基于 SRS (Simple Realtime Server) 的流媒体测试环境。 推流协议:RTMP (FFmpeg 模拟推流)拉流协议:WebRTC (低延迟播放)特性:视频循环播放、不保存…...
Spatial Audio(空间音频)与多声道环绕声:从5.1到7.1的沉浸式体验升级
1. 从立体声到环绕声:音频技术的进化之路 记得我第一次在朋友家体验5.1声道家庭影院时,那种子弹从耳边呼啸而过的感觉让我彻底震撼了。这完全颠覆了我对"好音质"的认知——原来声音可以如此立体、如此真实。要理解现代的空间音频技术…...
基于MATLAB的模拟退火粒子群算法在含分布式电源配电网多目标优化中的应用
310.基于matlab的模拟退火粒子群算法对含分布式电源的配电网进行多目标优化,目标函数包括总有功网损、总投资与运行成本、电压稳定欲度。 和目标函数相关参数有单位分布式电源投资成本、运行成本,分布式电源设备使用年限、贴现率等。 经过优化得到最佳结…...
【基于Tube的非线性系统模型预测控制MPC】基于鲁棒控制不变集的管式模型预测控制方案及其在利普希茨非线性系统中的应用附Matlab代码
✅作者简介:热爱科研的Matlab仿真开发者,擅长毕业设计辅导、数学建模、数据处理、建模仿真、程序设计、完整代码获取、论文复现及科研仿真。🍎 往期回顾关注个人主页:Matlab科研工作室👇 关注我领取海量matlab电子书和…...
手把手教你用kafka-storage.sh重新格式化Kafka KRaft集群数据目录(解决No meta.properties报错)
深入解析Kafka KRaft模式下数据目录重构与集群恢复实战指南 当你在深夜收到Kafka集群告警,发现所有节点因No meta.properties报错而集体罢工时,那种头皮发麻的感觉我太熟悉了。去年双十一大促前夜,我们因为临时调整存储路径而遭遇类似问题&am…...
Nano Banana API 来了:不到半价享官方同款品质,仅需约 ¥0.10/张!
最近被谷歌新发布的 Nano Banana(Gemini 2.5 Flash Image)图像生成模型 霸屏了。 从手办秒变真人级 Cosplay,到一键统一多图风格,从个性化头像到产品概念设计,甚至连静态画作都能一键生成电影级动态分镜——这波 AI 生…...
AutoSar标准文档下载全攻略:从官网入口到模块选择(附命名规则解析)
AutoSar标准文档高效获取与深度解析指南 引言 在汽车电子系统开发领域,AutoSar标准已经成为行业公认的架构规范。无论是ECU开发工程师、系统架构师还是测试验证人员,都需要频繁查阅AutoSar官方文档。然而,面对庞大的文档体系和复杂的命名规则…...
《QGIS快速入门与应用基础》240:指北针旋转与大小调整
作者:翰墨之道,毕业于国际知名大学空间信息与计算机专业,获硕士学位,现任国内时空智能领域资深专家、CSDN知名技术博主。多年来深耕地理信息与时空智能核心技术研发,精通 QGIS、GrassGIS、OSG、OsgEarth、UE、Cesium、OpenLayers、Leaflet、MapBox 等主流工具与框架,兼具…...
手把手教你解决Unity视频播放问题:H264编码设置与RawImage的正确用法
Unity视频播放全攻略:H264编码优化与RawImage实战解析 在Unity项目开发中,视频播放功能看似简单,却暗藏诸多技术细节。许多开发者都曾遇到过视频不同步、颜色失真或性能低下的困扰。本文将深入剖析视频播放的核心技术要点,从编码格…...
物联网水产养殖监控系统:智能联动,实现养殖设备自动调控
一、应用背景 水产养殖是我国农业经济的重要组成部分,传统养殖模式长期依赖人工巡检、经验判断,存在诸多难以破解的行业痛点,严重制约养殖效益与产业可持续发展。随着物联网、大数据、边缘计算、无线通信技术的成熟,搭建智能化、数…...
