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

wordpress后台更新后 前端没变化的解决方法

使用siteground主机的wordpress网站&#xff0c;会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后&#xff0c;网站没有变化的情况。 不熟悉siteground主机的新手&#xff0c;遇到这个问题&#xff0c;就很抓狂&#xff0c;明明是哪都没操作错误&#x…...

云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?

大家好&#xff0c;欢迎来到《云原生核心技术》系列的第七篇&#xff01; 在上一篇&#xff0c;我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在&#xff0c;我们就像一个拥有了一块崭新数字土地的农场主&#xff0c;是时…...

逻辑回归:给不确定性划界的分类大师

想象你是一名医生。面对患者的检查报告&#xff08;肿瘤大小、血液指标&#xff09;&#xff0c;你需要做出一个**决定性判断**&#xff1a;恶性还是良性&#xff1f;这种“非黑即白”的抉择&#xff0c;正是**逻辑回归&#xff08;Logistic Regression&#xff09;** 的战场&a…...

通过Wrangler CLI在worker中创建数据库和表

官方使用文档&#xff1a;Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后&#xff0c;会在本地和远程创建数据库&#xff1a; npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库&#xff1a; 现在&#xff0c;您的Cloudfla…...

Python实现prophet 理论及参数优化

文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候&#xff0c;写过一篇简单实现&#xff0c;后期随着对该模型的深入研究&#xff0c;本次记录涉及到prophet 的公式以及参数调优&#xff0c;从公式可以更直观…...

基于数字孪生的水厂可视化平台建设:架构与实践

分享大纲&#xff1a; 1、数字孪生水厂可视化平台建设背景 2、数字孪生水厂可视化平台建设架构 3、数字孪生水厂可视化平台建设成效 近几年&#xff0c;数字孪生水厂的建设开展的如火如荼。作为提升水厂管理效率、优化资源的调度手段&#xff0c;基于数字孪生的水厂可视化平台的…...

Python如何给视频添加音频和字幕

在Python中&#xff0c;给视频添加音频和字幕可以使用电影文件处理库MoviePy和字幕处理库Subtitles。下面将详细介绍如何使用这些库来实现视频的音频和字幕添加&#xff0c;包括必要的代码示例和详细解释。 环境准备 在开始之前&#xff0c;需要安装以下Python库&#xff1a;…...

Yolov8 目标检测蒸馏学习记录

yolov8系列模型蒸馏基本流程&#xff0c;代码下载&#xff1a;这里本人提交了一个demo:djdll/Yolov8_Distillation: Yolov8轻量化_蒸馏代码实现 在轻量化模型设计中&#xff0c;**知识蒸馏&#xff08;Knowledge Distillation&#xff09;**被广泛应用&#xff0c;作为提升模型…...

如何更改默认 Crontab 编辑器 ?

在 Linux 领域中&#xff0c;crontab 是您可能经常遇到的一个术语。这个实用程序在类 unix 操作系统上可用&#xff0c;用于调度在预定义时间和间隔自动执行的任务。这对管理员和高级用户非常有益&#xff0c;允许他们自动执行各种系统任务。 编辑 Crontab 文件通常使用文本编…...

c++第七天 继承与派生2

这一篇文章主要内容是 派生类构造函数与析构函数 在派生类中重写基类成员 以及多继承 第一部分&#xff1a;派生类构造函数与析构函数 当创建一个派生类对象时&#xff0c;基类成员是如何初始化的&#xff1f; 1.当派生类对象创建的时候&#xff0c;基类成员的初始化顺序 …...