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

【日常刷题】迷宫问题

描述

定义一个二维数组 N*M ,如 5 × 5 数组下所示:

int maze[5][5] = {
0, 1, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
};

它表示一个迷宫,其中的1表示墙壁,0表示可以走的路,只能横着走或竖着走,不能斜着走,要求编程序找出从左上角到右下角的路线。入口点为[0,0],既第一格是可以走的路。

输入描述

输入两个整数,分别表示二维数组的行数,列数。再输入相应的数组,其中的1表示墙壁,0表示可以走的路。数据保证有唯一解,不考虑有多解的情况,即迷宫只有一条通道。

输出描述

左上角到右下角的最短路径,格式如样例所示。

分析

这道题我们将要使用动态规划中的回溯的思想,因为我们不能保证走了一步之后,接下来的后几步仍然能走得通,所以我们最好使用递归,然后判断条件是否回溯.

代码

#include <iostream>
#include <vector>
using namespace std;
int ROW;
int COL;
vector<vector<int>> maze;
vector<vector<int>> path_tmp;
vector<vector<int>> path_best;void getbestpath(int i,int j)
{maze[i][j] = 1;path_tmp.push_back({i,j});//如果找到了出口if(i == ROW - 1 && j == COL - 1){//将临时路径和最佳路径进行比较if(path_best.empty() || path_best.size() > path_tmp.size()){//储存最佳路径path_best = path_tmp;}}//如果没有找到出口//向上查找if(i - 1 >= 0 && maze[i-1][j] == 0){getbestpath(i-1,j);}//向下查找if(i + 1 < ROW && maze[i+1][j] == 0){getbestpath(i+1,j);}//向左查找if(j - 1 >= 0 && maze[i][j-1] == 0){getbestpath(i,j-1);}//向右查找if(j + 1 < COL && maze[i][j+1] == 0){getbestpath(i,j+1);}//全部不可走->回溯maze[i][j] = 0;//开放该路径path_tmp.pop_back();
}int main() {while(cin >> ROW >> COL){maze = vector<vector<int>>(ROW,vector<int>(COL,0));// 定义迷宫for(int i = 0; i < ROW; i++)//输入迷宫{for(int j = 0; j < COL ; j++){cin >> maze[i][j];}}getbestpath(0,0);//从(0,0)开始走//打印结果for(int i = 0; i < path_best.size(); i++){cout << "(" << path_best[i][0] << "," << path_best[i][1] << ")" << endl;}}
}

相关文章:

【日常刷题】迷宫问题

描述 定义一个二维数组 N*M &#xff0c;如 5 5 数组下所示&#xff1a; int maze[5][5] { 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, }; 它表示一个迷宫&#xff0c;其中的1表示墙壁&#xff0c;0表示可以走的路&#xff0c;只能横着走…...

【Python童年游戏】满满的回忆杀—那些年玩过的童年游戏你还记得吗?那个才是你的菜?看到第一个我就泪奔了(致我们逝去的青春)

导语 滴一一学生卡&#x1f64c; 结伴上车的学生仔子们 用笑声打破车厢的沉默 大人眼里的晚高峰 是给放学后快乐&#x1f600;时光的加时 下车的学生匆匆起身带起 一阵熟悉的栀子香于&#x1f493; 是关于校园的记忆 开始零零散散地闪现 放学后集合的秘密基地/跟着城…...

C++ | 认识标准库string和vector

本文概要 本篇文章主要介绍C的标准库类型string和vector&#xff0c;文中描述和代码示例很详细&#xff0c;看完即可掌握&#xff0c;感兴趣的小伙伴快来一起学习吧。 &#x1f31f;&#x1f31f;&#x1f31f;个人简介 &#x1f31f;&#x1f31f;&#x1f31f; ☀️大家好&a…...

JAVA面试宝典: SpringCloud知识点(通俗易懂易背)

1、什么是 Spring Cloud&#xff1f; Spring Cloud 是基于 Spring Boot 的微服务架构开发工具箱&#xff0c;提供了在分布式系统中构建可靠的、弹性的、灵活的应用所需的大多数工具。Spring Cloud 中包含的子项目如下&#xff1a; Spring Cloud Config&#xff1a;配置管理工具…...

es学习笔记

集群环境下数据往哪个节点放? 路由计算&#xff1a;hash(id) %主分片的数量 集群环境下查数据怎么查&#xff1f; 分配控制&#xff1a;访问任何一个节点都能获取数据&#xff0c;随机访问到的这个节点称为协调节点&#xff08;访问了当前节点&#xff0c;不一定从当前节点…...

SAS学习第9章:卡方检验之适合性检验与独立性检验

卡方检验就是统计样本的实际观测值与理论推断值之间的偏离程度&#xff0c;实际观测值与理论推断值之间的偏离程度就决定卡方值的大小&#xff0c;如果卡方值越大&#xff0c;二者偏差程度越大&#xff1b;反之&#xff0c;二者偏差越小&#xff1b;若两个值完全相等时&#xf…...

马斯克爆料Twitter裁了八成员工;OpenAI CEO:GPT-5根本不存在;小鹏被曝年终奖打0.5折 | AI一周资讯

来源: AI前线 微信号&#xff1a;ai-front 整理 | 凌敏 微软宣布开源 Deep Speed Chat&#xff1b;消息称软银旗下 Arm 启动赴美 IPO&#xff1b;国家网信办出台生成式 AI 管理办法&#xff1b;前理想 AI 芯片一号位骄旸加入三星&#xff0c;负责组建 GPU 团队…… 资 讯 Op…...

ASEMI代理ADG1408YRUZ-REEL7原装ADI车规级ADG1408YRUZ-REEL7

编辑&#xff1a;ll ASEMI代理ADG1408YRUZ-REEL7原装ADI车规级ADG1408YRUZ-REEL7 型号&#xff1a;ADG1408YRUZ-REEL7 品牌&#xff1a;ADI /亚德诺 封装&#xff1a;TSSOP-16 批号&#xff1a;2023 安装类型&#xff1a;表面贴装型 引脚数量&#xff1a;16 类型&#…...

phpstudy本地环境搭建图文教程

作者&#xff1a;Eason_LYC 悲观者预言失败&#xff0c;十言九中。 乐观者创造奇迹&#xff0c;一次即可。 一个人的价值&#xff0c;在于他所拥有的。可以不学无术&#xff0c;但不能一无所有&#xff01; 技术领域&#xff1a;WEB安全、网络攻防 关注WEB安全、网络攻防。我的…...

【UE 控件蓝图】菜单及功能实现

素材资源连接&#xff1a;百度网盘 请输入提取码 密码&#xff1a;fvcw 效果 步骤 1. 创建蓝图&#xff0c;父类为“HUD” 命名为“MainMenuHUD”并打开 在事件图表中添加如下节点&#xff1a; 2. 创建控件蓝图&#xff0c;命名为“MainMenuWidget” 此时在“MainMenuHUD”的…...

Java 并发编程面试题——Future

目录 1.什么是 Future 模式&#xff1f;Java 中是如何实现的&#xff1f;2.Callable、Future 与 FutureTask 分别是什么&#xff1f;2.1.Callable 接口2.2.Future 接口2.3.FutureTask 类 3.CompletableFuture 类有什么用&#xff1f; 1.什么是 Future 模式&#xff1f;Java 中是…...

SpringBoot 介绍

1.简介 SpringBoot最开始基于Spring4.0设计&#xff0c;是由Pivotal公司提供的框架。 SpringBoot发展史&#xff1a; 2003年Rod Johnson成立Interface公司&#xff0c;产品是SpringFramework2004年&#xff0c;Spring框架开源&#xff0c;公司改名为Spring Source2008年&…...

自动驾驶作业手册

1 总 则 目的为保障港口内自动驾驶车辆安全使用,预防和减少事故,保护人民生命和财产安全,促进港口内业务开展。 含义和范围港口内自动驾驶车辆,是指电脑驾驶车辆,为一种运输动力的无人地面载具,与有人驾驶车辆不同,其具备不需要人类操作即可以感测其环境及导航功能,能…...

MySQL调优笔记——慢SQL优化记录(2)

今天调优的原因是&#xff0c;有一个统计报表业务&#xff0c;查询的时间太慢&#xff1b;同时由于数据库的压力是随机性的&#xff0c;这个业务的执行下限和上限相差近20倍&#xff1b;快的时候可以达到600ms&#xff0c;慢的时候有9秒之多&#xff1b; 接下来详细介绍&#x…...

二叉排序树的插入和删除操作(python实现)

二叉排序树的插入和删除操作都是在保持二叉排序树特性的前提下进行的。 插入操作&#xff1a; 在二叉排序树中插入一个新节点时&#xff0c;先比较新节点的值和当前节点的值的大小关系&#xff0c;若小于当前节点&#xff0c;则继续在当前节点的左子树中查找&#xff1b;若大…...

算法记录 | Day35 贪心算法

860.柠檬水找零 思路&#xff1a; 只需要维护三种金额的数量&#xff0c;5&#xff0c;10和20。 有如下三种情况&#xff1a; 情况一&#xff1a;账单是5&#xff0c;直接收下。情况二&#xff1a;账单是10&#xff0c;消耗一个5&#xff0c;增加一个10情况三&#xff1a;账…...

coinex // 撮合引擎 逻辑流程 (两种数据源 初始化源和前端源)

目录 1 生产者 数据源 1.1. match-server 一启动 初始化数据 自动查询数据库 查询level2要展示的数据 1.2 match-server接收 前端发给Exchange-server的数据 2. 将查询/接受的数据EntrustOrder 转成 Order 解耦 过滤掉不要的属性 3.Order转成 OrderEvent 4. 分配序号发布…...

CentOS7---部署LNMP数据存储到redis

一、部署LNMP及redis 1、部署LNMP&#xff0c;需要将 tengine-2.2.0.tar.gz 拷贝到虚拟机的 /root 目录下 步骤一&#xff1a;安装nginx 源码安装相关软件包 # pcre-devel做正则匹配&#xff0c;zlib-devel做数据压缩 [roottemplate ~]# yum -y install gcc pcre-devel zlib-de…...

Linux中的git命令行

Linux中的git命令行 目录 Linux中的git命令行引入1、Linux下的git工具起源2、gitee的使用.gitignore.git 3、git三板斧3.1 git add3.2 git commit3.3 git push 4、git操作4.1 查看提交日志4.2 查看状态4.3 远端同步4.4 删除文件4.5 修改文件名 引入 当多个开发者同时参与同一个…...

【C++】哈希表:开散列和闭散列

&#x1f4dd; 个人主页 &#xff1a;超人不会飞)&#x1f4d1; 本文收录专栏&#xff1a;《C的修行之路》&#x1f4ad; 如果本文对您有帮助&#xff0c;不妨点赞、收藏、关注支持博主&#xff0c;我们一起进步&#xff0c;共同成长&#xff01; 目录 前言一、基于哈希表的两个…...

铭豹扩展坞 USB转网口 突然无法识别解决方法

当 USB 转网口扩展坞在一台笔记本上无法识别,但在其他电脑上正常工作时,问题通常出在笔记本自身或其与扩展坞的兼容性上。以下是系统化的定位思路和排查步骤,帮助你快速找到故障原因: 背景: 一个M-pard(铭豹)扩展坞的网卡突然无法识别了,扩展出来的三个USB接口正常。…...

在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能

下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能&#xff0c;包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...

抖音增长新引擎:品融电商,一站式全案代运营领跑者

抖音增长新引擎&#xff1a;品融电商&#xff0c;一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中&#xff0c;品牌如何破浪前行&#xff1f;自建团队成本高、效果难控&#xff1b;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...

STM32标准库-DMA直接存储器存取

文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA&#xff08;Direct Memory Access&#xff09;直接存储器存取 DMA可以提供外设…...

Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器

第一章 引言&#xff1a;语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域&#xff0c;文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量&#xff0c;支撑着搜索引擎、推荐系统、…...

《通信之道——从微积分到 5G》读书总结

第1章 绪 论 1.1 这是一本什么样的书 通信技术&#xff0c;说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号&#xff08;调制&#xff09; 把信息从信号中抽取出来&am…...

图表类系列各种样式PPT模版分享

图标图表系列PPT模版&#xff0c;柱状图PPT模版&#xff0c;线状图PPT模版&#xff0c;折线图PPT模版&#xff0c;饼状图PPT模版&#xff0c;雷达图PPT模版&#xff0c;树状图PPT模版 图表类系列各种样式PPT模版分享&#xff1a;图表系列PPT模板https://pan.quark.cn/s/20d40aa…...

Mac下Android Studio扫描根目录卡死问题记录

环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中&#xff0c;提示一个依赖外部头文件的cpp源文件需要同步&#xff0c;点…...

技术栈RabbitMq的介绍和使用

目录 1. 什么是消息队列&#xff1f;2. 消息队列的优点3. RabbitMQ 消息队列概述4. RabbitMQ 安装5. Exchange 四种类型5.1 direct 精准匹配5.2 fanout 广播5.3 topic 正则匹配 6. RabbitMQ 队列模式6.1 简单队列模式6.2 工作队列模式6.3 发布/订阅模式6.4 路由模式6.5 主题模式…...

嵌入式学习笔记DAY33(网络编程——TCP)

一、网络架构 C/S &#xff08;client/server 客户端/服务器&#xff09;&#xff1a;由客户端和服务器端两个部分组成。客户端通常是用户使用的应用程序&#xff0c;负责提供用户界面和交互逻辑 &#xff0c;接收用户输入&#xff0c;向服务器发送请求&#xff0c;并展示服务…...