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

[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 的二维整数数组&#xff0c;用来表示一个迷宫&#xff0c;数组中只包含 0 或 1&#xff0c;其中 0 表示可以走的路&#xff0c;1 表示不可通过的墙壁。 最初&#xff0c;有一个人位于左上角 (1,1)(1,1) 处&#xff0c;已知该人每次可以向上、下、左、右任意一个方…...

C语言字符串左旋

一、前言 这个题目的完整题目是这样子的。 二、我们实现这个编程的思路 2.1暴力破解思想 假如有一个数组里面的字符串为”abcdef“&#xff0c;我们这时候就这样先将字符”a“移到最后再将其余的字符前移。 2.2三步移动法 同样我们还是假设一个数组里面存的是字符串”abcd…...

Linux 中断会产生嵌套吗?

文章目录 1. 前言2. Linux 中断是否会嵌套&#xff1f;2.1 分析背景2.2 中断处理抢占、嵌套可能性分析2.3 中断处理抢占、嵌套小结 3. 参考资料 1. 前言 限于作者能力水平&#xff0c;本文可能存在谬误&#xff0c;因此而给读者带来的损失&#xff0c;作者不做任何承诺。 2. …...

嵌入式ARM版本银河麒麟操作系统V10SP1安装OPenGauss数据库

前言&#xff1a; 官网提供了非常完整的openGauss安装步骤。 https://opengauss.org/zh/download/archive/列举一下个人的使用环境&#xff1a; 麒麟V10 rk3588工控板&#xff08;ARM&#xff09; openGauss-3.0.5&#xff08;极简版&#xff09;浏览一下官网&#xff0c;可以…...

深度学习八股文

Bert旨在通过联合左侧和右侧的上下文&#xff0c;从未标记文本中预训练出一个深度双向表示模型。因此&#xff0c;BERT可以通过增加一个额外的输出层来进行微调&#xff0c;就可以达到为广泛的任务创建State-of-the-arts 模型的效果&#xff0c;比如QA、语言推理任务。Bert的构…...

jquery 自整理

echarts官方&#xff1a;Documentation - Apache ECharts 1、CheckBox复选框 //选中事件&#xff08;页面点击&#xff09; $(#operateExit).on(ifChecked, function(){ $(input[name"operateExit"]).val(1); }); //非选中事件&#xff…...

MySQL | 加索引报错

报错信息 1170 - BLOB/TEXT column user_name used in key specification without a key length解决方案 分析 这个错误通常是因为尝试在一个包含BLOB或TEXT类型列的列上创建索引时没有指定键的长度。MySQL要求在使用BLOB或TEXT类型列作为索引键时&#xff0c;必须指定键的长…...

前端:自制年历

详细思路可以看我的另一篇文章《前端&#xff1a;自制月历》&#xff0c;基本思路一致&#xff0c;只是元素布局略有差异 ①获取起始位startnew Date(moment().format(yyyy-01-01)).getDay() ②获取总的格子数numMath.ceil(365/7)*7,这里用365或者366计算结果都是一样的371 …...

9.手写JavaScript大数相加问题

一、核心思想 找到两个字符串中最长的长度&#xff0c;对两个字符串在头位置补0达到相等的长度&#xff0c;相加时注意进位和类型转换&#xff0c;特别考虑当相加到第一位是如果仍然有进位不要忽略。此外&#xff0c;js中允许使用的最大的数字为 console.log("最大数&qu…...

FPGA开源项目分享——基于 DE1-SOC 的 String Art 实现

导语 今天继续康奈尔大学FPGA课程ECE 5760的典型案例分享——基于DE1-SOC的String Art实现。 &#xff08;更多其他案例请参考网站&#xff1a; Final Projects ECE 5760&#xff09; 1. 项目概述 项目网址 ECE 5760 Final Project 项目说明 String Art起源于19世纪的数学…...

通过 CLI 和引入的方式使用 React:基础入门

使用React 有两种使用方式&#xff0c;主要有以下几个原因: 灵活性和适应性: 引入的方式可以让开发者在现有的 HTML 页面中快速引入 React,无需设置完整的项目环境。这适合小型或原型项目。 CLI 方式则更适合用于构建大型复杂的 React 应用程序,因为它提供了更完整的项目结构和…...

第三资本:铸就辉煌非凡的资历

第三资本香港有限公司在在金融投资领域一直以专业精神和不懈追求获得良好名声,近几年在国际资本市场上更是写下了辉煌的章节。针对第三资本而言,专业是基本,也是成功的唯一途径。投资总监刘国海解释道:“金融从业者务必深入把握专业能力,对行业现状敏感,重视风险管控,才能在这个…...

基于激光雷达的袋装水泥智能装车系统有哪些优势?

激光雷达技术在水泥机械智能化中发挥着举足轻重的作用&#xff0c;特别在袋装水泥智能装车系统的应用中表现得尤为突出。 由因泰立科技精心打造的基于激光雷达的袋装水泥智能装车系统&#xff0c;不仅大幅缩短了装车码垛的时间&#xff0c;降低了工人的劳动强度&#xff0c;还显…...

实战自动化修改主机名

一、主程序 #!/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的协议开发的发射端&#xff0c;通过串口和模块通讯&#xff0c;默认波特率 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。 …...

一辆汽车的节拍时间是怎样的?

节拍时间&#xff0c;又称 takt time&#xff0c;是德语中“节奏”的意思。在汽车制造业中&#xff0c;它指的是按照客户需求和生产计划&#xff0c;生产一辆汽车所需的时间。这个时间是固定的&#xff0c;它决定了生产线上每个工序的操作速度和节奏&#xff0c;是生产线上所有…...

数据结构-合并两个有效数组

题目描述 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2&#xff0c;另有两个整数 m 和 n &#xff0c;分别表示 nums1 和 nums2 中的元素数目。 请你 合并 nums2 到 nums1 中&#xff0c;使合并后的数组同样按 非递减顺序 排列。 注意&#xff1a;最终&#xff0c;…...

华为2024年校招实习硬件-结构工程师机试题(四套)

华为2024年校招&实习硬件-结构工程师机试题&#xff08;四套&#xff09; &#xff08;共四套&#xff09;获取&#xff08;WX: didadidadidida313&#xff0c;加我备注&#xff1a;CSDN 华为硬件结构题目&#xff0c;谢绝白嫖哈&#xff09; 结构设计工程师&#xff0c;结…...

使用Pandas解决问题:对比两列数据取最大值的五种方法

目录 一、使用max方法 二、使用apply方法结合lambda函数 三、使用np.maximum函数 四、使用clip方法 五、使用where方法结合条件赋值 总结&#xff1a; 在数据处理和分析中&#xff0c;经常需要比较两个或多个列的值&#xff0c;并取其中的最大值。Pandas库作为Python…...

Python爬虫实战:研究MechanicalSoup库相关技术

一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...

聊一聊接口测试的意义有哪些?

目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开&#xff0c;首…...

Linux --进程控制

本文从以下五个方面来初步认识进程控制&#xff1a; 目录 进程创建 进程终止 进程等待 进程替换 模拟实现一个微型shell 进程创建 在Linux系统中我们可以在一个进程使用系统调用fork()来创建子进程&#xff0c;创建出来的进程就是子进程&#xff0c;原来的进程为父进程。…...

Python+ZeroMQ实战:智能车辆状态监控与模拟模式自动切换

目录 关键点 技术实现1 技术实现2 摘要&#xff1a; 本文将介绍如何利用Python和ZeroMQ消息队列构建一个智能车辆状态监控系统。系统能够根据时间策略自动切换驾驶模式&#xff08;自动驾驶、人工驾驶、远程驾驶、主动安全&#xff09;&#xff0c;并通过实时消息推送更新车…...

Rust 开发环境搭建

环境搭建 1、开发工具RustRover 或者vs code 2、Cygwin64 安装 https://cygwin.com/install.html 在工具终端执行&#xff1a; rustup toolchain install stable-x86_64-pc-windows-gnu rustup default stable-x86_64-pc-windows-gnu ​ 2、Hello World fn main() { println…...

C# winform教程(二)----checkbox

一、作用 提供一个用户选择或者不选的状态&#xff0c;这是一个可以多选的控件。 二、属性 其实功能大差不差&#xff0c;除了特殊的几个外&#xff0c;与button基本相同&#xff0c;所有说几个独有的 checkbox属性 名称内容含义appearance控件外观可以变成按钮形状checkali…...

Java中栈的多种实现类详解

Java中栈的多种实现类详解&#xff1a;Stack、LinkedList与ArrayDeque全方位对比 前言一、Stack类——Java最早的栈实现1.1 Stack类简介1.2 常用方法1.3 优缺点分析 二、LinkedList类——灵活的双端链表2.1 LinkedList类简介2.2 常用方法2.3 优缺点分析 三、ArrayDeque类——高…...

java 局域网 rtsp 取流 WebSocket 推送到前端显示 低延迟

众所周知 摄像头取流推流显示前端延迟大 传统方法是服务器取摄像头的rtsp流 然后客户端连服务器 中转多了&#xff0c;延迟一定不小。 假设相机没有专网 公网 1相机自带推流 直接推送到云服务器 然后客户端拉去 2相机只有rtsp &#xff0c;边缘服务器拉流推送到云服务器 …...

Docker环境下安装 Elasticsearch + IK 分词器 + Pinyin插件 + Kibana(适配7.10.1)

做RAG自己打算使用esmilvus自己开发一个&#xff0c;安装时好像网上没有比较新的安装方法&#xff0c;然后找了个旧的方法对应试试&#xff1a; &#x1f680; 本文将手把手教你在 Docker 环境中部署 Elasticsearch 7.10.1 IK分词器 拼音插件 Kibana&#xff0c;适配中文搜索…...

虚拟机网络不通的问题(这里以win10的问题为主,模式NAT)

当我们网关配置好了&#xff0c;DNS也配置好了&#xff0c;最后在虚拟机里还是无法访问百度的网址。 第一种情况&#xff1a; 我们先考虑一下&#xff0c;网关的IP是否和虚拟机编辑器里的IP一样不&#xff0c;如果不一样需要更改一下&#xff0c;因为我们访问百度需要从物理机…...