【NOI-题解】1431. 迷宫的第一条出路

文章目录

  • 一、前言
  • 二、问题
    • 问题:1431. 迷宫的第一条出路
  • 三、感谢

一、前言

二、问题

问题:1431. 迷宫的第一条出路

类型:深度搜索、回溯、路径打印


题目描述:

已知一 N×N 的迷宫,允许往上、下、左、右四个方向行走,现请你按照左、上、右、下顺序进行搜索,找出第一条从左上角到右下角的路径。

输入:

输入数据有若干行,第一行有一个自然数 N(N≤20),表示迷宫的大小;
其后有 N 行数据,每行有 N 个 0 或 1(数字之间没有空格,0 表示可以通过,1 表示不能通过),用以描述迷宫地图。入口在左上角 (1,1)处,出口在右下角(N,N) 处。
所有迷宫保证存在从入口到出口的可行路径。

输出:

输出数据仅一行,为按照要求的搜索顺序找到的从入口到出口的第一条路径(搜索顺序:左、上、右、下)。

样例:

输入:

4
0001
0100
0010
0110

输出:

(1,1)->(1,2)->(1,3)->(2,3)->(2,4)->(3,4)->(4,4)

在这里插入图片描述


1.分析问题

  1. 已知:N×N 的迷宫,允许往上、下、左、右四个方向行走。
  2. 未知:按照左、上、右、下顺序进行搜索,找出第一条从左上角到右下角的路径。
  3. 关系:深度搜索、回溯。

2.定义变量

  • 定义变量:n表示迷宫的大小;二维数组mg[30][30]存储迷宫信息,其中0代表可通行,1代表障碍;二维数组bj[1000][1000]用于记录路径上的坐标。
int n,mg[30][30],bj[1000][1000]; 

3.输入数据

//三、数据输入cin>>n; for(int i=1;i<=n;i++){string s;cin>>s;for(int j=1;j<=n;j++){mg[i][j]=s[j-1]-'0';}}

4.数据计算

  • 调用dfs(1,1,1)开始从左上角(1,1)搜索到右下角。
//四、数据计算 dfs(1,1,1);
  • 定义一个深度优先搜索(DFS)函数,用于递归探索迷宫路径。
int  dfs(int x,int y,int k){if(x<1||x>n||y<1||y>n||mg[x][y]!=0){return k;}bj[k][1]=x;bj[k][2]=y;mg[x][y]=1;if(x==n&&y==n){//五、输出结果 for(int i=1;i<=k;i++){cout<<"("<<bj[i][1]<<","<<bj[i][2]<<")";if(i!=k){cout<<"->";}}}//左 dfs(x,y-1,k+1); //上dfs(x-1,y,k+1);//右dfs(x,y+1,k+1);//下 dfs(x+1,y,k+1);
}

完整代码如下:

#include<bits/stdc++.h> // 包含C++常用库函数
using namespace std; // 使用std命名空间以简化代码int n, // 迷宫的尺寸mg[30][30], // 用于存储迷宫地图,0表示可通过,1表示障碍bj[1000][1000]; // 记录搜索过程中的路径坐标// 深度优先搜索函数
// 参数: x, y 当前坐标;k 走过的步数(也作为bj数组的索引)
int dfs(int x, int y, int k){// 判断当前位置是否合法或已被访问if(x < 1 || x > n || y < 1 || y > n || mg[x][y] != 0){return k; // 不合法或已访问过,返回当前步数}// 记录路径bj[k][1] = x;bj[k][2] = y;mg[x][y] = 1; // 标记当前格子已访问// 如果到达右下角,输出路径并结束if(x == n && y == n){for(int i = 1; i <= k; i++){cout << "(" << bj[i][1] << "," << bj[i][2] << ")";if(i != k){ // 非最后一项添加箭头cout << "->";}}}// 递归搜索四个方向dfs(x, y-1, k+1); // 左dfs(x-1, y, k+1); // 上dfs(x, y+1, k+1); // 右dfs(x+1, y, k+1); // 下// 注意:此函数设计上没有直接利用返回值,实际搜索中无需返回具体值
}int main(){// 输入迷宫尺寸cin >> n; // 输入并构建迷宫地图for(int i = 1; i <= n; i++){string s;cin >> s;for(int j = 1; j <= n; j++){mg[i][j] = s[j-1] - '0'; // 字符转数字,'0' ASCII值为48,因此减去'0'得到数字}}// 开始搜索dfs(1, 1, 1); // 从(1,1)开始搜索,初始步数为1return 0; // 程序正常结束
}

三、感谢

如若本文对您的学习或工作有所启发和帮助,恳请您给予宝贵的支持——轻轻一点,为文章点赞;若觉得内容值得分享给更多朋友,欢迎转发扩散;若认为此篇内容具有长期参考价值,敬请收藏以便随时查阅。

每一次您的点赞、分享与收藏,都是对我持续创作和分享的热情鼓励,也是推动我不断提供更多高质量内容的动力源泉。期待我们在下一篇文章中再次相遇,共同攀登知识的高峰!

在这里插入图片描述

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

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

相关文章

git管理(Linux版本)

在Linux中我们如何把自己的代码上传到gitee中呢&#xff0c;本期将为大家讲解详细的步骤。 目录 查看Linux环境是否存在git工具 在gitee上创建代码仓库 复制仓库的HTTP路径到Linux中 代码上传 在仓库下创建文件或者将文件移动到仓库下 使用三板斧进行文件的上传 add …

网络安全复习笔记

概述 要素 CIA&#xff1a;可用性&#xff1b;完整性&#xff1b;保密性。 可控性&#xff1b;不可否认性&#xff1b;可审查性。 攻击 被动&#xff1a;窃听 - 保密性&#xff1b;监听 - 保密性主动&#xff1a;假冒 - 完整性&#xff1b;重放 - 完整性&#xff1b;改写 -…

2024年6月22日(星期六)骑行谷仓坝

2024年6月22日 (星期六) 骑行谷仓坝&#xff0c;早8:00到8:30&#xff0c; 龙泉小学门口(北京路尽头&#xff0c;高架桥下&#xff09;&#xff0c;9:00准时出发 【因迟到者&#xff0c;骑行速度快者&#xff0c;可自行追赶偶遇。】 偶遇地点:集合 &#xff0c;家住东&#xf…

phpStudy安装sqli-labs

phpStudy安装sqli-labs git地址&#xff1a;https://github.com/Audi-1/sqli-labs 点击管理–>根目录 将git下载的sqli-labs文件放进去并解压 进入sql-connections修改 修改db-creds.inc文件为自己数据库的账号密码 更改php版本为5.*&#xff0c;因为这个程序只能在php 5.…

《庆余年》在前,《玫瑰的故事》在后,阅文发现“新大陆”?

奋笔疾书的网文作家&#xff0c;即将迎来网络文学的高光时代。 近日&#xff0c;阅文集团于安徽省举办2024阅文创作大会。现场数据显示&#xff0c;2023年阅文活跃作家平均收入增长32%&#xff0c;创造近五年最大增幅。其中&#xff0c;中位数作家收入增幅达135%&#xff0c;已…

ECharts 雷达图案例001-自定义节点动画

ECharts 雷达图案例001-自定义节点动画 引言 在数据可视化的领域中&#xff0c;ECharts 提供了一种强大的工具来展示多维数据。本文将介绍如何使用 ECharts 创建一个自定义节点样式的雷达图&#xff0c;让数据展示更加生动和个性化。 效果预览 通过自定义节点样式&#xff…

echarts 折线图 实现某两个点之间不要连线

通过插入null或NaN的数据点来实现"断开"的效果 const data [[a, 1], [b, 2], [c, 3], [d, 4], [e, 5]] data.splice(2, 0, NaN) option {xAxis: {type: "category",data: [a, b, c, d, e]},yAxis: {},series: [{data,type: "line"}] }

【Matlab编程学习】 | matlab语言编程基础:常用图形绘制基础学习

&#x1f3a9; 欢迎来到技术探索的奇幻世界&#x1f468;‍&#x1f4bb; &#x1f4dc; 个人主页&#xff1a;一伦明悦-CSDN博客 ✍&#x1f3fb; 作者简介&#xff1a; C软件开发、Python机器学习爱好者 &#x1f5e3;️ 互动与支持&#xff1a;&#x1f4ac;评论 &…

上位机图像处理和嵌入式模块部署(h750 mcu和usb虚拟串口)

【 声明&#xff1a;版权所有&#xff0c;欢迎转载&#xff0c;请勿用于商业用途。 联系信箱&#xff1a;feixiaoxing 163.com】 对于mcu usb而言&#xff0c;大部分情况下&#xff0c;它和上位机之间的关系都是device的关系。一般usb&#xff0c;可以分成host和device。如果mc…

Mysql启动报错:本地计算机上的mysql服务启动后停止,某些服务在未由其他服务或程序使用时将自动停止

某天开机,发现Mysql被异常关闭,并且启动不起来,出这篇文章也是为了下次遇到类似问题,迅速解决(请细读文章,因为第二个方案才是主要方案) 第一个解决方案 我采用的第一个方法查“端口占用“问题(因为这是一篇博客所以我写的操作比较详细为了方便后面看这篇博客的人,我自…

创建第一个Springboot项目(环境准备、环境存在的问题、启动时存在的问题、启动的方式)

一、环境准备 专业版创建springboot&#xff0c;直接有一个选项可以选择 社区版&#xff0c;需要下载一个spring的插件 不要直接点 install 因为这个插件是付费的&#xff0c;直接点安装只有30天使用期限 在里面找免费版本的下载 然后安装 安装完成后&#xff0c;这个插件名会变…

云计算【第一阶段(16)】安装及管理程序

目录 一、linux 应用程序基础 1.1、应用程序与系统命令的关系 1.2、典型应用程序的目录结构 1.3、常见的软件包封装类型 二、RPM软件包管理工具 2.1、rpm命令的格式 2.2、安装&#xff0c;升级&#xff0c;卸载 rpm软件包 安装软件包 升级软件包 卸载软件包 查询软件…

数学建模基础:统计模型

目录 前言 一、概率与统计基础 二、统计模型 三、Matlab统计工具箱 四、实例示范&#xff1a;市场调查分析 步骤 1&#xff1a;数据导入 步骤 2&#xff1a;数据可视化 步骤 3&#xff1a;建立多元线性回归模型 步骤 4&#xff1a;模型验证 步骤 5&#xff1a;模型应…

vue+intro.js实现引导功能

前言&#xff1a; 使用 intro.js这个插件&#xff0c;来实现一个引导性的效果&#xff0c;适用场景&#xff0c;比如&#xff1a;新手引导页&#xff0c;操作说明等等 效果图&#xff1a; 官网地址&#xff1a;点我 实现步骤&#xff1a; 1、安装 npm install intro.js --sa…

【Netty】nio处理acceptreadwrite事件

&#x1f4dd;个人主页&#xff1a;五敷有你 &#x1f525;系列专栏&#xff1a;Netty ⛺️稳中求进&#xff0c;晒太阳 1.处理accept 1.1客户端代码 public class Client {public static void main(String[] args) {try (Socket socket new Socket("localhost…

【Cloudscapes V2】Blender商城10周年免费领取礼物超逼真的Vdb云和爆炸合集烟雾体积云字体符号轨迹火焰粒子

6月19号的限时免费领取插件挺牛的&#xff0c;可以在blender里渲染体积云、爆炸特效、火焰、烟雾等效果&#xff0c;非常逼真。 Blender商城10周年免费领取礼物&#xff1a;https://blendermarket.com/birthday Cloudscapes V2 - 超逼真的 Vdb 云和爆炸合集 CloudScapes 是 …

如何快速在一台新电脑上安装 Python 环境

一、下载miniconda 1.下载 我们可以在清华大学开源软件镜像站下载最新版本的miniconda。如&#xff1a;https://mirrors.tuna.tsinghua.edu.cn/anaconda/miniconda/Miniconda3-py38_4.9.2-Windows-x86_64.exe 2.安装 双击exe文件安装&#xff0c;如果没有特殊的需求&#x…

C# 索引器与迭代器分部类详情

文章目录 一、迭代器二、查看Foreach执行中间语言三、foreach实现过程总结四、实现迭代器最常用的方法五、分布类概述及其使用六、索引器概述及声明七、索引器在类中的使用八、索引器在接口中的使用九、总结 一、迭代器 1、迭代器&#xff08;iterator&#xff09;解决的是集合…

vue3+ts+vite集成eslint

项目中安装eslint yarn add eslint -Deslint初始化 npx eslint --init按照下方操作即可 安装typescript-eslint/parser yarn add typescript-eslint/parser -D安装vite-plugin-eslint2 yarn add vite-plugin-eslint2 -D配置vite-plugin-eslint2 // vite.config.ts import …

Linux系统编程——进程信号

目录 一&#xff0c;信号预备 1.1 生活中的信号 1.2 技术应用中的信号 1.3 signal函数捕捉信号 1.3 信号的发送与记录 1.4 信号的常见处理方式 二&#xff0c;信号的产生 2.1 核心转储 2.1.1 环境配置 2.1.2 利用core文件进行调试 2.1.3 core dump标志 2.2 通过系统…