当前位置: 首页 > news >正文

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>
#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 多终点迷宫问题

题目&#xff1a; 样例&#xff1a; 输入 3 3 0 0 0 1 0 0 0 1 0 输出 0 1 2 -1 2 3 -1 -1 4 思路&#xff1a; 单纯的 BFS 迷宫问题&#xff0c;只是标记一下每个点的 step&#xff0c;注意初始化答案数组都为 -1. 代码详解如下&#xff1a; #include <iostream> #…...

ES6中对象新增了哪些扩展?

一、属性的简写 当对象字面量的属性名与变量名相同时&#xff0c;可以省略属性名&#xff0c;直接使用变量名作为属性名。 const x 10; const y 20;// ES6之前 const obj1 { x: x, y: y };// ES6属性简写 const obj2 { x, y };注意&#xff1a;简写的对象方法不能用作构造…...

蓝桥杯每日一题2023.9.22

4960. 子串简写 - AcWing题库 题目描述 题目分析 原本为纯暴力但是发现会超时&#xff0c;可以加入前缀和&#xff0c;从前往后先记录一下每个位置c1出现的次数 再从前往后扫一遍&#xff0c;如果遇到c2就将答案加上此位置前的所有c1的个数&#xff08;直接加上此位置的前缀…...

vscode左键无法跳转到定义的文件

之前用vscode的时候&#xff0c;明明是可以ctrl键鼠标左键跳转到定义文件的&#xff0c;突然之间就不行了&#xff0c;鼠标移到引入上根本都没有下划线&#xff0c;无法跳转 解决方法&#xff1a; 项目的根目录新建 jsconfig.json 文件&#xff0c;代码如下 {"compiler…...

c、c++排序的相关知识(归并排序、计数排序、稳定性等)

排序&#xff0c;是对给定的一组数&#xff0c;按照某种逻辑关系&#xff0c;进行位置上的移动。由于排序至少需要将所有数过一遍&#xff08;正常情况下&#xff0c;非特殊数组&#xff09;&#xff0c;因此排序的时间复杂度一定不能小于O&#xff08;N&#xff09;。 归并排…...

oracle定时任务的使用

常见错误&#xff1a; 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 学得已经差不多了&#xff0c;基本都会了&#xff0c;现在开始向其他游戏脚本框架进发&#xff0c; Lua 语言很强大&#xff0c;就不多说&#xff0c; 按键精灵、触动精灵等等都是用该语言编程脚本的&#xff0c;由于按键精灵、触动精灵 和 AutoJS 类似,不是…...

JS合并2个远程pdf

要在HTML和JavaScript中读取远程PDF文件的矢量数据并合并两个PDF文件&#xff0c;您可以使用pdf-lib和Axios库。以下是使用pdf-lib和Axios在HTML和JavaScript中读取和合并远程PDF文件的步骤&#xff1a; 1. 引入 首先&#xff0c;确保您在HTML文件中引入了pdf-lib和Axios库。…...

TikTok的伦理挑战:虚拟世界与现实世界的交汇

在数字时代&#xff0c;社交媒体平台已经不再只是一个信息传播的工具&#xff0c;它已经深刻地改变了我们的社交行为、价值观和伦理观。 而在这一领域的佼佼者之一&#xff0c;TikTok&#xff0c;正面临着伦理挑战&#xff0c;这是虚拟世界与现实世界交汇的产物。 本文将深入…...

C# 获取磁盘空间大小的方法

方法一&#xff1a;利用System.IO.DriveInfo.GetDrives方法来获取 /// 获取指定驱动器的空间总大小(单位为B)////// 只需输入代表驱动器的字母即可 &#xff08;大写&#xff09;///public static long GetHardDiskSpace(string str_HardDiskName){long totalSize new long();…...

JVM机制理解与调优方案

作者&#xff1a;逍遥Sean 简介&#xff1a;一个主修Java的Web网站\游戏服务器后端开发者 主页&#xff1a;https://blog.csdn.net/Ureliable 觉得博主文章不错的话&#xff0c;可以三连支持一下~ 如有需要我的支持&#xff0c;请私信或评论留言&#xff01; 前言 很多Java开发…...

Django的设计模式及模板层

Django的设计模式及模板层 设计模式MVC和MVT MVC 代表 Model-View-Controller(模型-视图-控制器)模式。 M 模型层(Model),主要用于对数据库层的封装 V 视图层(View),用于向用户展示结果 (WHAT HOW) C 控制(Controller&#xff0c;用于处理请求、获取数据、返回结果(重要) 作…...

写代码生成流程图

我们在写文档&#xff0c;博客的时候&#xff0c;一般都会使用markdown语法&#xff0c;最常见的就是一些github开源项目的README。有时候会去画一些流程图&#xff0c;例如使用process.on或者xmind等第三方网站&#xff0c;然后截图插入到文档中。 今天我们介绍一种使用代码直…...

python reportlab生成pdf

这里自定义了pagetemplate&#xff0c;使用BaseDocTemplate&#xff0c;但我感觉一般使用SimpleDocTemplate就可以。 from reportlab.platypus import Frame from reportlab.lib.pagesizes import A4, landscapepadding dict(leftPadding72,rightPadding72,topPadding72,bott…...

第一次作业题解

第一次作业题解 P5717 【深基3.习8】三角形分类 思路 考的是if()的使用,还要给三条边判断大小 判断优先级&#xff1a; 三角形&#xff1f;直角、钝角、锐角等腰等边 判断按题给顺序来 代码 #include <stdio.h> int main() {int a 0, b 0, c 0, x 0, y 0, z 0…...

美篇作文网教学资源源码-自带作文数据

非常漂亮的UI设计和页面排版&#xff01; 自适应手机pc端 页面内容均支持自定义 可以用来做网站矩阵&#xff0c;或者增强你其他网站板块&#xff0c;或者单独运营都可以。 可以通过广告方式变现&#xff0c;或者引流等等 友好的seo&#xff0c;更容易被浏览器收录 关注青狐…...

电脑软件:Duplicate Cleaner Pro 5.16 重复文件清理软件(附下载)

大家平时在使用电脑的时候&#xff0c;会经常从网上下载文件或者从其他电脑拷贝文件到自己的电脑上。久而久之就会在电脑中存放很多相同的文件&#xff0c;并且会越积越多&#xff0c;不仅占用很多磁盘空间&#xff0c;在文件管理上也非常混乱不方便。如何解决呢&#xff1f; …...

支持笔记本电脑直插直充,TOWE 65W智能快充PDU超级插座

电源插排在我们的生活中是必不可少的电器配件。今天&#xff0c;我们日常生活中所使用的电子设备越来越多&#xff0c;无论是手机、平板、笔记本电脑还是各种家用电器&#xff0c;都需要电源来驱动。虽然相对于其他电器来说&#xff0c;插排结构比较简单&#xff0c;但现代家庭…...

部署Kafka

kafka&#xff1a;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、...

RestClient

什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端&#xff0c;它允许HTTP与Elasticsearch 集群通信&#xff0c;而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级&#xff…...

利用最小二乘法找圆心和半径

#include <iostream> #include <vector> #include <cmath> #include <Eigen/Dense> // 需安装Eigen库用于矩阵运算 // 定义点结构 struct Point { double x, y; Point(double x_, double y_) : x(x_), y(y_) {} }; // 最小二乘法求圆心和半径 …...

DockerHub与私有镜像仓库在容器化中的应用与管理

哈喽&#xff0c;大家好&#xff0c;我是左手python&#xff01; Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库&#xff0c;用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...

[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?

论文网址&#xff1a;pdf 英文是纯手打的&#xff01;论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误&#xff0c;若有发现欢迎评论指正&#xff01;文章偏向于笔记&#xff0c;谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...

江苏艾立泰跨国资源接力:废料变黄金的绿色供应链革命

在华东塑料包装行业面临限塑令深度调整的背景下&#xff0c;江苏艾立泰以一场跨国资源接力的创新实践&#xff0c;重新定义了绿色供应链的边界。 跨国回收网络&#xff1a;废料变黄金的全球棋局 艾立泰在欧洲、东南亚建立再生塑料回收点&#xff0c;将海外废弃包装箱通过标准…...

sqlserver 根据指定字符 解析拼接字符串

DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...

令牌桶 滑动窗口->限流 分布式信号量->限并发的原理 lua脚本分析介绍

文章目录 前言限流限制并发的实际理解限流令牌桶代码实现结果分析令牌桶lua的模拟实现原理总结&#xff1a; 滑动窗口代码实现结果分析lua脚本原理解析 限并发分布式信号量代码实现结果分析lua脚本实现原理 双注解去实现限流 并发结果分析&#xff1a; 实际业务去理解体会统一注…...

Pinocchio 库详解及其在足式机器人上的应用

Pinocchio 库详解及其在足式机器人上的应用 Pinocchio (Pinocchio is not only a nose) 是一个开源的 C 库&#xff0c;专门用于快速计算机器人模型的正向运动学、逆向运动学、雅可比矩阵、动力学和动力学导数。它主要关注效率和准确性&#xff0c;并提供了一个通用的框架&…...

用机器学习破解新能源领域的“弃风”难题

音乐发烧友深有体会&#xff0c;玩音乐的本质就是玩电网。火电声音偏暖&#xff0c;水电偏冷&#xff0c;风电偏空旷。至于太阳能发的电&#xff0c;则略显朦胧和单薄。 不知你是否有感觉&#xff0c;近两年家里的音响声音越来越冷&#xff0c;听起来越来越单薄&#xff1f; —…...

Java数值运算常见陷阱与规避方法

整数除法中的舍入问题 问题现象 当开发者预期进行浮点除法却误用整数除法时,会出现小数部分被截断的情况。典型错误模式如下: void process(int value) {double half = value / 2; // 整数除法导致截断// 使用half变量 }此时...