当前位置: 首页 > 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…...

19c补丁后oracle属主变化,导致不能识别磁盘组

补丁后服务器重启&#xff0c;数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后&#xff0c;存在与用户组权限相关的问题。具体表现为&#xff0c;Oracle 实例的运行用户&#xff08;oracle&#xff09;和集…...

7.4.分块查找

一.分块查找的算法思想&#xff1a; 1.实例&#xff1a; 以上述图片的顺序表为例&#xff0c; 该顺序表的数据元素从整体来看是乱序的&#xff0c;但如果把这些数据元素分成一块一块的小区间&#xff0c; 第一个区间[0,1]索引上的数据元素都是小于等于10的&#xff0c; 第二…...

JavaScript 中的 ES|QL:利用 Apache Arrow 工具

作者&#xff1a;来自 Elastic Jeffrey Rengifo 学习如何将 ES|QL 与 JavaScript 的 Apache Arrow 客户端工具一起使用。 想获得 Elastic 认证吗&#xff1f;了解下一期 Elasticsearch Engineer 培训的时间吧&#xff01; Elasticsearch 拥有众多新功能&#xff0c;助你为自己…...

c++ 面试题(1)-----深度优先搜索(DFS)实现

操作系统&#xff1a;ubuntu22.04 IDE:Visual Studio Code 编程语言&#xff1a;C11 题目描述 地上有一个 m 行 n 列的方格&#xff0c;从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子&#xff0c;但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...

DBAPI如何优雅的获取单条数据

API如何优雅的获取单条数据 案例一 对于查询类API&#xff0c;查询的是单条数据&#xff0c;比如根据主键ID查询用户信息&#xff0c;sql如下&#xff1a; select id, name, age from user where id #{id}API默认返回的数据格式是多条的&#xff0c;如下&#xff1a; {&qu…...

零基础设计模式——行为型模式 - 责任链模式

第四部分&#xff1a;行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习&#xff01;行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想&#xff1a;使多个对象都有机会处…...

NLP学习路线图(二十三):长短期记忆网络(LSTM)

在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...

大学生职业发展与就业创业指导教学评价

这里是引用 作为软工2203/2204班的学生&#xff0c;我们非常感谢您在《大学生职业发展与就业创业指导》课程中的悉心教导。这门课程对我们即将面临实习和就业的工科学生来说至关重要&#xff0c;而您认真负责的教学态度&#xff0c;让课程的每一部分都充满了实用价值。 尤其让我…...

return this;返回的是谁

一个审批系统的示例来演示责任链模式的实现。假设公司需要处理不同金额的采购申请&#xff0c;不同级别的经理有不同的审批权限&#xff1a; // 抽象处理者&#xff1a;审批者 abstract class Approver {protected Approver successor; // 下一个处理者// 设置下一个处理者pub…...

Leetcode33( 搜索旋转排序数组)

题目表述 整数数组 nums 按升序排列&#xff0c;数组中的值 互不相同 。 在传递给函数之前&#xff0c;nums 在预先未知的某个下标 k&#xff08;0 < k < nums.length&#xff09;上进行了 旋转&#xff0c;使数组变为 [nums[k], nums[k1], …, nums[n-1], nums[0], nu…...