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

洛谷B3625迷宫寻路

迷宫寻路

题目描述

机器猫被困在一个矩形迷宫里。

迷宫可以视为一个 n × m n\times m n×m 矩阵,每个位置要么是空地,要么是墙。机器猫只能从一个空地走到其上、下、左、右的空地。

机器猫初始时位于 ( 1 , 1 ) (1, 1) (1,1) 的位置,问能否走到 ( n , m ) (n, m) (n,m) 位置。

输入格式

第一行,两个正整数 n , m n,m n,m

接下来 n n n 行,输入这个迷宫。每行输入一个长为 m m m 的字符串,# 表示墙,. 表示空地。

输出格式

仅一行,一个字符串。如果机器猫能走到 ( n , m ) (n, m) (n,m),则输出 Yes;否则输出 No

样例 #1

样例输入 #1

3 5
.##.#
.#...
...#.

样例输出 #1

Yes

提示

样例解释

路线如下: ( 1 , 1 ) → ( 2 , 1 ) → ( 3 , 1 ) → ( 3 , 2 ) → ( 3 , 3 ) → ( 2 , 3 ) → ( 2 , 4 ) → ( 2 , 5 ) → ( 3 , 5 ) (1,1)\to (2,1) \to (3,1) \to (3,2)\to (3,3) \to (2, 3) \to (2, 4) \to (2, 5) \to (3, 5) (1,1)(2,1)(3,1)(3,2)(3,3)(2,3)(2,4)(2,5)(3,5)

数据规模与约定

对于 100 % 100\% 100% 的数据,保证 1 ≤ n , m ≤ 100 1 \leq n, m \leq 100 1n,m100,且 ( 1 , 1 ) (1,1) (1,1) ( n , m ) (n, m) (n,m) 均为空地。

运用bfs来解决
一开始机器猫在(0,0)位置,要走到(n-1,m-1)位置
边界条件:x、y大于0且分别小于n、m,每一点都只能走一次(通过bool数组记载是否走过),下一次要走的位置上不是#。

#include<bits/stdc++.h>
using namespace std;int n,m;
const int N = 110;
char path[N][N];
bool st[N][N];
int X[4] = {-1,0,1,0};
int Y[4] = {0,-1,0,1};bool bfs()
{//BFS使用一个队列来存储待访问的节点。//队列的特性是先进先出(FIFO),这确保了BFS是逐层访问节点的。queue<pair<int,int>> q;//创建一个队列来存储待访问节点q.push({0,0});//将起始节点(0,0)入队st[0][0] = true;//标记起始节点为已访问while(!q.empty())//当队列不为空时,继续搜索{int x = q.front().first;//取出队列中的第一个节点的坐标int y = q.front().second;q.pop();//弹出队列中的第一个节点if(x == n-1 && y == m-1)//如果当前节点是目标节点,则返回 true{return true;}//遍历当前节点的四个相邻方向for(int i = 0;i < 4;i++){int dx = x + X[i];//计算新节点的 x 坐标int dy = y + Y[i];//计算新节点的 y 坐标//检查新节点是否在网格范围内、是否未被访问过、以及是否是可通过的节点if(dx >= 0 && dy >= 0 && dx < n&& dy < m && !st[dx][dy] && path[dx][dy] != '#'){st[dx][dy] = true;//标记新节点为已访问q.push({dx,dy});//将新节点加入队列,以便后续访问它的相邻节点}}}return false;//如果队列为空且没有找到目标节点,则返回 false
}int main()
{cin >> n >> m;for(int i = 0;i < n;i++){for(int j = 0;j < m;j++){cin >> path[i][j];st[i][j] = false;}}if(bfs()){cout << "Yes" <<endl;}else{cout << "No" <<endl;}return 0;
}

扩展

获取单一行走路径:

#include<bits/stdc++.h>
using namespace std;int n, m;
const int N = 110;
char path[N][N];
bool st[N][N];
pair<int, int> previous[N][N]; // 用于记录每个节点的父节点
int X[4] = {-1, 0, 1, 0};
int Y[4] = {0, -1, 0, 1};bool bfs() {queue<pair<int, int>> q;q.push({0, 0});st[0][0] = true;while (!q.empty()) {int x = q.front().first;int y = q.front().second;q.pop();if (x == n - 1 && y == m - 1) {return true; // 找到目标节点,返回true表示找到路径}for (int i = 0; i < 4; i++) {int dx = x + X[i];int dy = y + Y[i];if (dx >= 0 && dy >= 0 && dx < n && dy < m && !st[dx][dy] && path[dx][dy] != '#') {st[dx][dy] = true;previous[dx][dy] = {x, y}; // 记录父节点q.push({dx, dy});}}}return false; // 无法到达目标节点
}void printPath() {int x = n - 1, y = m - 1;vector<pair<int, int>> path;// 回溯到起点,构建路径while (x != 0 || y != 0) {path.push_back({x, y});pair<int, int> p = previous[x][y];x = p.first;y = p.second;}path.push_back({0, 0}); // 添加起点// 打印路径(从起点到终点)for (int i = path.size() - 1; i >= 0; i--) {cout << "(" << path[i].first << "," << path[i].second << ") ";}cout << endl;
}int main() {cin >> n >> m;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cin >> path[i][j];st[i][j] = false;previous[i][j] = {-1, -1}; // 初始化为无效值}}if (bfs()) {cout << "Yes" << endl;printPath(); // 打印路径} else {cout << "No" << endl;}return 0;
}

在这段代码中,增加了一个previous数组来记录每个节点的父节点。当找到目标节点时,bfs函数返回true,然后调用printPath函数来回溯并打印出从起点到终点的路径。
bfs部分详解:

void printPath() {  int x = n - 1, y = m - 1; // 从终点开始回溯  vector<pair<int, int>> path; // 用于存储路径上的节点坐标  // 回溯到起点,构建路径  while (x != 0 || y != 0) { // 当还没有回溯到起点时继续循环  path.push_back({x, y}); // 将当前节点坐标添加到路径中  pair<int, int> p = previous[x][y]; // 获取当前节点的父节点坐标  x = p.first; // 更新x坐标为父节点的x坐标  y = p.second; // 更新y坐标为父节点的y坐标  }  path.push_back({0, 0}); // 添加起点到路径中,因为上面的循环条件导致起点不会被添加  // 打印路径(从起点到终点),注意这里是从后往前打印,因为路径是从起点开始记录的  for (int i = path.size() - 1; i >= 0; i--) {  cout << "(" << path[i].first << "," << path[i].second << ") "; // 打印每个节点的坐标  }  cout << endl; // 打印换行  
}

printPath 函数是用于打印从起点(0,0)到终点(n-1, m-1)在迷宫中的具体路径的。这个函数通过回溯的方式,利用在广度优先搜索(BFS)过程中记录的每个节点的父节点信息,来重建整条路径。

这个函数的工作流程如下:

  1. 初始化终点坐标 (x, y)(n-1, m-1)
  2. 创建一个空的 vector 容器 path,用于存储路径上的节点坐标。
  3. 使用 while 循环进行回溯,条件是当前节点不是起点(即 x != 0 || y != 0)。
    • 在循环中,首先将当前节点的坐标 (x, y) 添加到 path 中。
    • 然后,通过查询 prev 数组获取当前节点的父节点坐标,并将父节点坐标赋值给 (x, y),以便在下一次循环中继续回溯。
  4. 循环结束后,将起点坐标 (0, 0) 添加到 path 中,因为回溯过程是从终点开始,到起点结束,但由于循环条件的限制,起点并未被包含在内,所以需要手动添加。
  5. 最后,使用 for 循环逆序打印 path 中的节点坐标。这是因为路径在 path 中是以从终点到起点的顺序存储的,而我们需要按照从起点到终点的顺序打印出来。

通过这个函数,我们就可以在控制台上看到从起点到终点的完整路径了。

相关文章:

洛谷B3625迷宫寻路

迷宫寻路 题目描述 机器猫被困在一个矩形迷宫里。 迷宫可以视为一个 n m n\times m nm 矩阵&#xff0c;每个位置要么是空地&#xff0c;要么是墙。机器猫只能从一个空地走到其上、下、左、右的空地。 机器猫初始时位于 ( 1 , 1 ) (1, 1) (1,1) 的位置&#xff0c;问能否…...

GPT-SoVITS 测试

开箱直用版&#xff08;使用 AutoDL&#xff09; step1 打开地址 https://www.codewithgpu.com/i/RVC-Boss/GPT-SoVITS/GPT-SoVITS-Official 选择 AutoDL创建实例&#xff0c;选择 3080ti 机器 step2 创建好实例之后&#xff0c;进入命令行&#xff0c;输入命令 echo {}>…...

人工智能:更多有用的 Python 库

目录 前言 推荐 JupyterLab 入门 复杂的矩阵运算 其它人工智能和机器学习的 Python 库 前言 在这篇文章中&#xff0c;我们将了解更多的矩阵操作&#xff0c;同时再介绍几个人工智能 Python 库。 推荐 前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#x…...

Linux BIO如何下发到HDD?

在Linux操作系统中&#xff0c;当创建一个Block I/O请求&#xff08;BIO&#xff09;时&#xff0c;它会被封装成适合硬件交互的数据结构&#xff0c;并通过内核存储子系统传递到对应的硬件控制器上&#xff0c;如SAS&#xff08;Serial Attached SCSI&#xff09;HBA&#xff…...

《动手学深度学习(PyTorch版)》笔记4.6

注&#xff1a;书中对代码的讲解并不详细&#xff0c;本文对很多细节做了详细注释。另外&#xff0c;书上的源代码是在Jupyter Notebook上运行的&#xff0c;较为分散&#xff0c;本文将代码集中起来&#xff0c;并加以完善&#xff0c;全部用vscode在python 3.9.18下测试通过。…...

Hadoop-MapReduce-源码跟读-客户端篇

一、源码下载 下面是hadoop官方源码下载地址&#xff0c;我下载的是hadoop-3.2.4&#xff0c;那就一起来看下吧 Index of /dist/hadoop/core 二、从WordCount进入源码 用idea将源码加载进来后&#xff0c;找到org.apache.hadoop.examples.WordCount类&#xff08;快捷方法&…...

《游戏-03_3D-开发》之—新输入系统人物移动攻击连击

本次修改unity的新输入输出系统。本次修改unity需要重启&#xff0c;请先保存项目&#xff0c; 点击加号起名为MyCtrl&#xff0c; 点击加号设置为一轴的&#xff0c; 继续设置W键&#xff0c; 保存 生成自动脚本&#xff0c; 修改MyPlayer代码&#xff1a; using UnityEngine;…...

滴水逆向三期笔记与作业——02C语言——10 Switch语句反汇编

滴水逆向三期笔记与作业——02C语言——10 Switch语句反汇编 一、Switch语句1、switch语句 是if语句的简写2、break加与不加有什么特点?default语句可以省略吗&#xff1f;3、游戏中的switch语句&#xff08;示例&#xff09;4、添加case后面的值&#xff0c;一个一个增加&…...

燃烧的指针(三)

&#x1f308;个人主页&#xff1a;小田爱学编程 &#x1f525; 系列专栏&#xff1a;c语言从基础到进阶 &#x1f3c6;&#x1f3c6;关注博主&#xff0c;随时获取更多关于c语言的优质内容&#xff01;&#x1f3c6;&#x1f3c6; &#x1f600;欢迎来到小田代码世界~ &#x…...

微服务架构实施攻略:如何选择合适的微服务通信机制?

随着业务的快速发展和系统的日益复杂&#xff0c;传统的单体应用逐渐显露出瓶颈&#xff0c;已无法满足现代软件研发的需求。微服务架构作为一种灵活、可扩展的解决方案&#xff0c;通过将复杂系统拆分为一系列小型服务来提高系统的可伸缩性、灵活性和可维护性。在实施微服务架…...

【jetson笔记】解决vscode远程调试qt.qpa.xcb: could not connect to display报错

配置x11转发 jetson远程安装x11转发 安装Xming Xming下载 安装完成后打开安装目录C:\Program Files (x86)\Xming 用记事本打开X0.hosts文件&#xff0c;添加jetson IP地址 后续IP改变需要重新修改配置文件 localhost 192.168.107.57打开Xlaunch Win菜单搜索Xlaundch打开 一…...

网络安全产品之认识安全隔离网闸

文章目录 一、什么是安全隔离网闸二、安全隔离网闸的主要功能三、安全隔离网闸的工作原理四、安全隔离网闸的分类五、安全隔离网闸与防火墙的区别四、安全隔离网闸的应用场景 随着互联网的发展&#xff0c;网络攻击和病毒传播的方式越来越复杂&#xff0c;对网络安全的要求也越…...

Java通过模板替换实现excel的传参填写

以模板为例子 将上面$转义的内容替换即可 package com.gxuwz.zjh.util;import org.apache.poi.ss.usermodel.*; import org.apache.poi.xssf.usermodel.XSSFWorkbook; import java.io.*; import java.util.HashMap; import java.util.Map; import java.io.IOException; impor…...

眼底增强型疾病感知蒸馏模型 FDDM:无需配对,fundus 指导 OCT 分类

眼底增强型疾病感知蒸馏模型 FDDM&#xff1a;fundus 指导 OCT 分类 核心思想设计思路训练和推理 效果总结子问题: 疾病特定特征的提取与蒸馏子问题: 类间关系的理解与建模 核心思想 论文&#xff1a;https://arxiv.org/pdf/2308.00291.pdf 代码&#xff1a;https://github.c…...

代码随想录算法刷题训练营day17

代码随想录算法刷题训练营day17&#xff1a;LeetCode(110)平衡二叉树 LeetCode(110)平衡二叉树 题目 代码 /*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(…...

Java集合如何选择

为什么使用集合 当需要存储一组类型相同的数据时&#xff0c;数组是最常用且最基本的容器之一。但是&#xff0c;使用数组存储对象存在一些不足之处&#xff0c;因为在实际开发中&#xff0c;存储的数据类型多种多样且数量不确定。这时&#xff0c;Java 集合就派上用场了。与数…...

简单介绍----微服务和Spring Cloud

微服务和SpringCloud 1.什么是微服务&#xff1f; 微服务是将一个大型的、单一的应用程序拆分成多个小型服务&#xff0c;每个服务负责实现特定的业务功能&#xff0c;并且可以通过网络通信与其他服务通信。微服务的优点是开发更灵活&#xff08;不同的微服务可以使用不同的开…...

Jenkins邮件推送配置

目录 涉及Jenkins插件&#xff1a; 邮箱配置 什么是授权码 在第三方客户端/服务怎么设置 IMAP/SMTP 设置方法 POP3/SMTP 设置方法 获取授权码&#xff1a; Jenkins配置 从Jenkins主面板System configuration>System进入邮箱配置 在Email Extension Plugin 邮箱插件…...

硬件知识(1) 手机的长焦镜头

#灵感# 手机总是配备好几个镜头&#xff0c;研究一下 目录 手机常配备的摄像头&#xff0c;及效果举例 长焦的焦距 焦距的定义和示图&#xff1a; IPC的焦距和适用场景&#xff1a; 手机常配备的摄像头&#xff0c;及效果举例 以下是小米某个手机的摄像头介绍&#xff1a…...

华为机考入门python3--(3)牛客3-明明的随机数

分类&#xff1a;集合、排序 知识点&#xff1a; 集合添加元素 set.add(element) 集合转列表 list(set) 列表排序 list.sort() 题目来自【牛客】 N int(input().strip()) nums set()for i in range(N):nums.add(int(input().strip()))# 集合转列表 nums_list l…...

docker详细操作--未完待续

docker介绍 docker官网: Docker&#xff1a;加速容器应用程序开发 harbor官网&#xff1a;Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台&#xff0c;用于将应用程序及其依赖项&#xff08;如库、运行时环…...

ESP32读取DHT11温湿度数据

芯片&#xff1a;ESP32 环境&#xff1a;Arduino 一、安装DHT11传感器库 红框的库&#xff0c;别安装错了 二、代码 注意&#xff0c;DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...

[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?

论文网址&#xff1a;pdf 英文是纯手打的&#xff01;论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误&#xff0c;若有发现欢迎评论指正&#xff01;文章偏向于笔记&#xff0c;谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...

剑指offer20_链表中环的入口节点

链表中环的入口节点 给定一个链表&#xff0c;若其中包含环&#xff0c;则输出环的入口节点。 若其中不包含环&#xff0c;则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用

1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...

ios苹果系统,js 滑动屏幕、锚定无效

现象&#xff1a;window.addEventListener监听touch无效&#xff0c;划不动屏幕&#xff0c;但是代码逻辑都有执行到。 scrollIntoView也无效。 原因&#xff1a;这是因为 iOS 的触摸事件处理机制和 touch-action: none 的设置有关。ios有太多得交互动作&#xff0c;从而会影响…...

Map相关知识

数据结构 二叉树 二叉树&#xff0c;顾名思义&#xff0c;每个节点最多有两个“叉”&#xff0c;也就是两个子节点&#xff0c;分别是左子 节点和右子节点。不过&#xff0c;二叉树并不要求每个节点都有两个子节点&#xff0c;有的节点只 有左子节点&#xff0c;有的节点只有…...

分布式增量爬虫实现方案

之前我们在讨论的是分布式爬虫如何实现增量爬取。增量爬虫的目标是只爬取新产生或发生变化的页面&#xff0c;避免重复抓取&#xff0c;以节省资源和时间。 在分布式环境下&#xff0c;增量爬虫的实现需要考虑多个爬虫节点之间的协调和去重。 另一种思路&#xff1a;将增量判…...

视频行为标注工具BehaviLabel(源码+使用介绍+Windows.Exe版本)

前言&#xff1a; 最近在做行为检测相关的模型&#xff0c;用的是时空图卷积网络&#xff08;STGCN&#xff09;&#xff0c;但原有kinetic-400数据集数据质量较低&#xff0c;需要进行细粒度的标注&#xff0c;同时粗略搜了下已有开源工具基本都集中于图像分割这块&#xff0c…...

何谓AI编程【02】AI编程官网以优雅草星云智控为例建设实践-完善顶部-建立各项子页-调整排版-优雅草卓伊凡

何谓AI编程【02】AI编程官网以优雅草星云智控为例建设实践-完善顶部-建立各项子页-调整排版-优雅草卓伊凡 背景 我们以建设星云智控官网来做AI编程实践&#xff0c;很多人以为AI已经强大到不需要程序员了&#xff0c;其实不是&#xff0c;AI更加需要程序员&#xff0c;普通人…...