[C++][算法基础]走迷宫(BFS)
给定一个 n×m 的二维整数数组,用来表示一个迷宫,数组中只包含 0 或 1,其中 0 表示可以走的路,1 表示不可通过的墙壁。
最初,有一个人位于左上角 (1,1)(1,1) 处,已知该人每次可以向上、下、左、右任意一个方向移动一个位置。
请问,该人从左上角移动至右下角 (n,m)处,至少需要移动多少次。
数据保证 (1,1)(1,1) 处和 (n,m) 处的数字为 00,且一定至少存在一条通路。
输入格式
第一行包含两个整数 n 和 m。
接下来 n 行,每行包含 m 个整数(0 或 1),表示完整的二维数组迷宫。
输出格式
输出一个整数,表示从左上角移动至右下角的最少移动次数。
数据范围
1≤n,m≤100
输入样例:
5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
输出样例:
8
代码:
#include<iostream>
#include<queue>
using namespace std;const int N = 110;int n,m;
int G[N][N];
int dist[N][N];
queue<pair<int,int>> Q;int bfs(){int head = 0,tail = 0;int dx[4] = {0,1,0,-1}, dy[4] = {1,0,-1,0};dist[0][0] = 0;Q.push({0,0});while(Q.size()!=0){auto now = Q.front();Q.pop();for(int i = 0;i < 4;i++){int x = now.first + dx[i];int y = now.second + dy[i];if(x >= 0 && x < n && y >= 0 && y < m && G[x][y] == 0 &&dist[x][y] == -1){dist[x][y] = dist[now.first][now.second] + 1;Q.push({x,y});}}}return dist[n-1][m-1];
}int main(){cin>>n>>m;for(int i = 0;i < n;i++){for(int j = 0;j < m;j++){cin>>G[i][j];dist[i][j] = -1;}}cout<<bfs();return 0;
}
相关文章:
[C++][算法基础]走迷宫(BFS)
给定一个 nm 的二维整数数组,用来表示一个迷宫,数组中只包含 0 或 1,其中 0 表示可以走的路,1 表示不可通过的墙壁。 最初,有一个人位于左上角 (1,1)(1,1) 处,已知该人每次可以向上、下、左、右任意一个方…...
C语言字符串左旋
一、前言 这个题目的完整题目是这样子的。 二、我们实现这个编程的思路 2.1暴力破解思想 假如有一个数组里面的字符串为”abcdef“,我们这时候就这样先将字符”a“移到最后再将其余的字符前移。 2.2三步移动法 同样我们还是假设一个数组里面存的是字符串”abcd…...
Linux 中断会产生嵌套吗?
文章目录 1. 前言2. Linux 中断是否会嵌套?2.1 分析背景2.2 中断处理抢占、嵌套可能性分析2.3 中断处理抢占、嵌套小结 3. 参考资料 1. 前言 限于作者能力水平,本文可能存在谬误,因此而给读者带来的损失,作者不做任何承诺。 2. …...
嵌入式ARM版本银河麒麟操作系统V10SP1安装OPenGauss数据库
前言: 官网提供了非常完整的openGauss安装步骤。 https://opengauss.org/zh/download/archive/列举一下个人的使用环境: 麒麟V10 rk3588工控板(ARM) openGauss-3.0.5(极简版)浏览一下官网,可以…...
深度学习八股文
Bert旨在通过联合左侧和右侧的上下文,从未标记文本中预训练出一个深度双向表示模型。因此,BERT可以通过增加一个额外的输出层来进行微调,就可以达到为广泛的任务创建State-of-the-arts 模型的效果,比如QA、语言推理任务。Bert的构…...
jquery 自整理
echarts官方:Documentation - Apache ECharts 1、CheckBox复选框 //选中事件(页面点击) $(#operateExit).on(ifChecked, function(){ $(input[name"operateExit"]).val(1); }); //非选中事件ÿ…...
MySQL | 加索引报错
报错信息 1170 - BLOB/TEXT column user_name used in key specification without a key length解决方案 分析 这个错误通常是因为尝试在一个包含BLOB或TEXT类型列的列上创建索引时没有指定键的长度。MySQL要求在使用BLOB或TEXT类型列作为索引键时,必须指定键的长…...
前端:自制年历
详细思路可以看我的另一篇文章《前端:自制月历》,基本思路一致,只是元素布局略有差异 ①获取起始位startnew Date(moment().format(yyyy-01-01)).getDay() ②获取总的格子数numMath.ceil(365/7)*7,这里用365或者366计算结果都是一样的371 …...
9.手写JavaScript大数相加问题
一、核心思想 找到两个字符串中最长的长度,对两个字符串在头位置补0达到相等的长度,相加时注意进位和类型转换,特别考虑当相加到第一位是如果仍然有进位不要忽略。此外,js中允许使用的最大的数字为 console.log("最大数&qu…...
FPGA开源项目分享——基于 DE1-SOC 的 String Art 实现
导语 今天继续康奈尔大学FPGA课程ECE 5760的典型案例分享——基于DE1-SOC的String Art实现。 (更多其他案例请参考网站: Final Projects ECE 5760) 1. 项目概述 项目网址 ECE 5760 Final Project 项目说明 String Art起源于19世纪的数学…...
通过 CLI 和引入的方式使用 React:基础入门
使用React 有两种使用方式,主要有以下几个原因: 灵活性和适应性: 引入的方式可以让开发者在现有的 HTML 页面中快速引入 React,无需设置完整的项目环境。这适合小型或原型项目。 CLI 方式则更适合用于构建大型复杂的 React 应用程序,因为它提供了更完整的项目结构和…...
第三资本:铸就辉煌非凡的资历
第三资本香港有限公司在在金融投资领域一直以专业精神和不懈追求获得良好名声,近几年在国际资本市场上更是写下了辉煌的章节。针对第三资本而言,专业是基本,也是成功的唯一途径。投资总监刘国海解释道:“金融从业者务必深入把握专业能力,对行业现状敏感,重视风险管控,才能在这个…...
基于激光雷达的袋装水泥智能装车系统有哪些优势?
激光雷达技术在水泥机械智能化中发挥着举足轻重的作用,特别在袋装水泥智能装车系统的应用中表现得尤为突出。 由因泰立科技精心打造的基于激光雷达的袋装水泥智能装车系统,不仅大幅缩短了装车码垛的时间,降低了工人的劳动强度,还显…...
实战自动化修改主机名
一、主程序 #!/bin/bash# 设置主机名为node01 set_hostname() {local new_hostname$1echo "正在设置主机名为 $new_hostname ..."# 使用hostnamectl设置主机名hostnamectl set-hostname $new_hostname# 检查主机名是否更改成功if [ "$(hostname)" "…...
无人机GB42590接收端 +接收端,同时支持2.4G与5.8G双频WIFI模组
严格按照GB42590的协议开发的发射端,通过串口和模块通讯,默认波特率 921600。 http://www.doit.am/首页-深圳四博智联科技有限公司-淘宝网https://shop144145132.taobao.com/?spma230r.7195193.1997079397.2.71f6771dJHT2r0 二、接口文档 单片机和模…...
PVE系统的安装
一.PVE系统的安装 前置准备环境:windows电脑已安装Oracle VM VirtualBox,电脑支持虚拟化,且已经开启,按住ctrl+shift+ESC打开任务管理器查看是否开启,如果被禁用,可进入BIOS开启虚拟化,重启电脑后再进行后续操作。本步骤选用windows10安装VirtualBox,版本为7.0.8。 …...
一辆汽车的节拍时间是怎样的?
节拍时间,又称 takt time,是德语中“节奏”的意思。在汽车制造业中,它指的是按照客户需求和生产计划,生产一辆汽车所需的时间。这个时间是固定的,它决定了生产线上每个工序的操作速度和节奏,是生产线上所有…...
数据结构-合并两个有效数组
题目描述 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2,另有两个整数 m 和 n ,分别表示 nums1 和 nums2 中的元素数目。 请你 合并 nums2 到 nums1 中,使合并后的数组同样按 非递减顺序 排列。 注意:最终,…...
华为2024年校招实习硬件-结构工程师机试题(四套)
华为2024年校招&实习硬件-结构工程师机试题(四套) (共四套)获取(WX: didadidadidida313,加我备注:CSDN 华为硬件结构题目,谢绝白嫖哈) 结构设计工程师,结…...
使用Pandas解决问题:对比两列数据取最大值的五种方法
目录 一、使用max方法 二、使用apply方法结合lambda函数 三、使用np.maximum函数 四、使用clip方法 五、使用where方法结合条件赋值 总结: 在数据处理和分析中,经常需要比较两个或多个列的值,并取其中的最大值。Pandas库作为Python…...
网络六边形受到攻击
大家读完觉得有帮助记得关注和点赞!!! 抽象 现代智能交通系统 (ITS) 的一个关键要求是能够以安全、可靠和匿名的方式从互联车辆和移动设备收集地理参考数据。Nexagon 协议建立在 IETF 定位器/ID 分离协议 (…...
从WWDC看苹果产品发展的规律
WWDC 是苹果公司一年一度面向全球开发者的盛会,其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具,对过去十年 WWDC 主题演讲内容进行了系统化分析,形成了这份…...
基于ASP.NET+ SQL Server实现(Web)医院信息管理系统
医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上,开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识,在 vs 2017 平台上,进行 ASP.NET 应用程序和简易网站的开发;初步熟悉开发一…...
.Net框架,除了EF还有很多很多......
文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...
YSYX学习记录(八)
C语言,练习0: 先创建一个文件夹,我用的是物理机: 安装build-essential 练习1: 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件,随机修改或删除一部分,之后…...
IT供电系统绝缘监测及故障定位解决方案
随着新能源的快速发展,光伏电站、储能系统及充电设备已广泛应用于现代能源网络。在光伏领域,IT供电系统凭借其持续供电性好、安全性高等优势成为光伏首选,但在长期运行中,例如老化、潮湿、隐裂、机械损伤等问题会影响光伏板绝缘层…...
Fabric V2.5 通用溯源系统——增加图片上传与下载功能
fabric-trace项目在发布一年后,部署量已突破1000次,为支持更多场景,现新增支持图片信息上链,本文对图片上传、下载功能代码进行梳理,包含智能合约、后端、前端部分。 一、智能合约修改 为了增加图片信息上链溯源,需要对底层数据结构进行修改,在此对智能合约中的农产品数…...
代码规范和架构【立芯理论一】(2025.06.08)
1、代码规范的目标 代码简洁精炼、美观,可持续性好高效率高复用,可移植性好高内聚,低耦合没有冗余规范性,代码有规可循,可以看出自己当时的思考过程特殊排版,特殊语法,特殊指令,必须…...
Linux部署私有文件管理系统MinIO
最近需要用到一个文件管理服务,但是又不想花钱,所以就想着自己搭建一个,刚好我们用的一个开源框架已经集成了MinIO,所以就选了这个 我这边对文件服务性能要求不是太高,单机版就可以 安装非常简单,几个命令就…...
在鸿蒙HarmonyOS 5中使用DevEco Studio实现指南针功能
指南针功能是许多位置服务应用的基础功能之一。下面我将详细介绍如何在HarmonyOS 5中使用DevEco Studio实现指南针功能。 1. 开发环境准备 确保已安装DevEco Studio 3.1或更高版本确保项目使用的是HarmonyOS 5.0 SDK在项目的module.json5中配置必要的权限 2. 权限配置 在mo…...
