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;
}

最后提交:

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

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

相关文章

常用接口测试工具

首先&#xff0c;什么是接口呢&#xff1f; 接口一般来说有两种&#xff0c;一种是程序内部的接口&#xff0c;一种是系统对外的接口。 系统对外的接口&#xff1a;比如你要从别的网站或服务器上获取资源或信息&#xff0c;别人肯定不会把数据库共享给你&#xff0c;他只能给你…

五、3d场景的卡片展示的创建

在我们3d的开发中&#xff0c;对某一些建筑和物体进行解释说明是非常常见的现象&#xff0c;那么就不得不说卡片的展示了&#xff0c;卡片展示很友好的说明了当前物体的状态&#xff0c;一目了然&#xff0c;下面就是效果图。 它主要有两个方法来实现&#xff0c;大量的图片建议…

最近很火的AIGC人工智能之AI赋能运营(巧用ChatGPT轻松上手新媒体)

前言 「作者主页」&#xff1a;雪碧有白泡泡 「个人网站」&#xff1a;雪碧的个人网站 「推荐专栏」&#xff1a; ★java一站式服务 ★ ★ React从入门到精通★ ★前端炫酷代码分享 ★ ★ 从0到英雄&#xff0c;vue成神之路★ ★ uniapp-从构建到提升★ ★ 从0到英雄&#xff…

阿里云服务器技术创新、网络技术和数据中心技术说明

阿里云服务器技术创新、网络技术创新、数据中心技术创新和智能运维&#xff1a;云服务器方升架构、自研硬件、自研存储硬件AliFlash和异构计算加速平台&#xff0c;以及全自研网络系统技术创新和数据中心巴拿马电源、液冷技术等技术创新说明&#xff0c;阿里云百科分享阿里云服…

算法-堆/多路归并-查找和最小的 K 对数字

算法-堆/多路归并-查找和最小的 K 对数字 1 题目概述 1.1 题目出处 https://leetcode.cn/problems/find-k-pairs-with-smallest-sums/description/?envTypestudy-plan-v2&envIdtop-interview-150 1.2 题目描述 2 优先级队列构建大顶堆 2.1 思路 将两个数字的和放入大…

Spring面试题23:Spring支持哪些事务管理类型?Spring框架的事务管理有哪些优点?你更倾向用哪种事务管理类型?

该文章专注于面试,面试只要回答关键点即可,不需要对框架有非常深入的回答,如果你想应付面试,是足够了,抓住关键点 面试官:Spring支持哪些事务管理类型? Spring 支持以下几种事务管理类型: 编程式事务管理:通过在代码中显式地使用事务管理 API(如 TransactionTempla…

英飞凌 Tricore 架构中断系统详解

本文以TC3系列MCU为例&#xff0c;先来了解中断源是如何产生的&#xff0c;再看一下CPU是如何处理中断源的。 AURIX TC3XX的中断路由模块 Interrupt Router (IR) 在TC3中&#xff0c;中断既可以被CPU处理&#xff0c;也可以被DMA处理&#xff0c;所以手册中不再把中断称为中断…

Spring 学习(九)整合 Mybatis

1. 整合 Mybatis 步骤 导入相关 jar 包 <dependencies><dependency><groupId>junit</groupId><artifactId>junit</artifactId><version>4.12</version><scope>test</scope></dependency><dependency>…

软件测试/测试开发丨岗位内推-58同城岗位开放~

58同城-测试工程师 岗位职责 1.参与需求分析、设计评审&#xff0c;制定测试计划&#xff0c;设计测试用例&#xff0c;搭建测试环境&#xff1b; 2.执行各级别和类型的测试&#xff0c;参与互联网测试的全流程&#xff1b; 3.借助最前沿的研发技术和理念&#xff0c;通过测…

短视频矩阵源码saas版开发---技术成品打磨

短视频矩阵源码saas版开发---技术成品打磨 企业要不要做抖音&#xff1f; 我的答案是要&#xff0c;而且要快&#xff0c;原因有以下几点&#xff1a; 1. 抖音高速增长未停&#xff0c;流量红利还未完全释放完&#xff0c;仍然有增长空间&#xff1b; 2. 抖音变现能力越来越…

《家的温暖,国庆团圆》

目录 &#x1f4d6; 引言 &#x1f4dd; 假日放假表 &#x1f365; 中秋节 &#x1f4da; 中秋节的由来 中秋节的仪式 &#x1f4da; 赏月 &#x1f4da; 吃月饼 &#x1f4da; 猜灯谜 &#x1f4da; 品茶赏花 &#x1f4da; 舞狮龙 &#x1f4da; 中秋节的感触 &am…

C++项目笔记--基于TensorRT搭建一个YoloV5服务器

目录 1--项目描述 2--项目地址 3--编译运行 4--测试结果 5--补充说明 1--项目描述 ① 基于 C/S 模型来构建 TCP 服务器和 TCP 客户端。 ② 使用 Epoll 来监控服务器和客户端之间的连接。 ③ 服务器和客户端约定使用相同的数据传输协议&#xff0c;头部分别使用 4 个字节来…

OpenCV查找和绘制轮廓:findContours和drawContours

1 任务描述&#xff1a; 绘制图中粗线矩形的2个边界&#xff0c;并找到其边界的中心线 图1 原始图像 2.函数原型 findContours( InputOutputArray image, OutputArrayOfArrays contours, OutputArray hierarchy, int mode, …

【C++】string 之 find、rfind、replace、compare函数的学习

前言 上篇文章&#xff0c;我们学习了assign、at、append这三个函数 今天&#xff0c;我们来学习find、 函数 find函数 引入 我们都知道&#xff0c;find函数可以是string类中&#xff0c;用于查找字符或者字符串的函数 也可以是&#xff0c;<algorithm>头文件中&am…

什么是Selenium?使用Selenium进行自动化测试!

你知道什么是 Selenium 吗&#xff1f;你知道为什么要使用它吗&#xff1f;答案就在本文中&#xff0c;很高兴能够与你共飧。 自动化测试正席卷全球&#xff0c;Selenium 认证是业界最抢手的技能之一。 什么是 Selenium&#xff1f; Selenium 是一种开源工具&#xff0c;用于…

96 # cookie

cookie 和 session 和 sessionStorage 和 localStorage localStorage 和 sessionStorage 本地储存&#xff08;发送请求不会携带&#xff09;&#xff0c;不能跨域localStorage 浏览器关闭后不会清空&#xff0c;必须手动清空sessionStorage 浏览器关闭后就会销毁http 无状态的…

如何使用 API 接口获取商品数据,从申请 API 接口、使用 API 接口到实际应用,一一讲解

在当今的数字化时代&#xff0c;应用程序接口&#xff08;API&#xff09;已经成为数据获取的重要通道。API 接口使得不同的应用程序能够方便地进行数据交换&#xff0c;从而促进了信息的广泛传播和利用。在众多的数据源中&#xff0c;商品数据是一个非常重要的领域&#xff0c…

postman怎么进行参数化?

一、先准备好参数化数据 &#xff08;参数化数据可以使用Excel或者txt的文件。 注意如果使用的是txt的文件&#xff0c;一定要使用英文的逗号&#xff0c;不然的话会报错&#xff01;&#xff09; 注意&#xff1a;填写好的数据后&#xff0c;保存的时候需要另存为&#xff0c…

接口自动化测试:pytest基础讲解

为什么要做接⼝测试&#xff1f; 只靠前端测试很难确保很⾼的覆盖率。接⼝测试&#xff0c;可以模拟出各种类型的⼊参&#xff0c;包括⼀些在前端模拟不出来的⼊参&#xff0c;还能根据接⼝⽂档的定义&#xff0c;设计出相对完善的⼊参值&#xff0c;在接⼝层保证质量&#xff…

燃尽图是什么?如何用它提升敏捷项目流程?

**敏捷项目管理**的核心是透明度和持续改进。燃尽图是轻松实现这两点的秘密武器。这种动态的可视化工具能有效地说明团队在一段时间内的进展情况&#xff0c;突出显示剩余的工作&#xff0c;并揭示你的团队是否在实现目标的正轨上。 敏捷项目管理中的燃尽图 燃尽图是敏捷项目…