迷宫最短路径求解--c++

【代码】
#include<iostream>
#include<queue>
#include<stack>
using namespace std;
#define ROW 8
#define COL 8
//测试迷宫数据
int maze[ROW][COL] = {{0,0,0,1,0,0,0,0},{0,1,0,1,0,1,0,1},{0,1,0,0,0,1,0,1},{0,1,0,1,1,1,0,1},{0,1,0,1,1,0,0,0},{0,1,1,0,0,0,1,1},{0,0,0,0,1,0,1,1},{1,1,1,0,0,0,0,0}
};typedef struct
{int index; //当前点在路径结点数组中的位置int parent_idx; //当前经过点的上一个点在路径结点数组中的位置int x, y; //当前点的坐标
}PathNode;
//迷宫中每个点第一次出现时放入数组,为后续查找路径提供信息
PathNode path[ROW * COL];
//已访问数组,表示每个点是否已被访问
bool vis[ROW][COL] = { false };
//方向结构体
typedef struct
{int xstep, ystep;
}Dir;
Dir dir[4] = { {-1,0},{0,-1},{1,0},{0,1} };
bool validate(int x, int y)
{return x >= 0 && x < ROW && y >= 0 && y < COL;
}
//根据出口结点反向查找路径
void identifyPath(PathNode node)
{stack<PathNode>s;int skips = 0;//从最后一个节点逐次入栈,反向找到最短路径上的每个点while (true){s.push(node);if (node.parent_idx == -1)break;node = path[node.parent_idx];}cout << "path:" << endl;while (!s.empty()){node = s.top();s.pop();cout << "(" << node.x << "," << node.y << ")";if (!s.empty()){skips++;cout << "->";}}cout << endl;cout << "path length:" << skips << endl;
}//寻找以(sx,xy)为起点,(ex,ey)为出口的迷宫路径
//使用图的广度优先遍历,从起点开始逐层往外扩散,直到出现出口坐标
void findShortestPath(int sx, int sy, int ex, int ey)
{PathNode pn;int idx = 0;int cnt = 0;//初始化,生成开始结点信息,并放入路径数组中pn.parent_idx = -1;pn.x = sx;pn.y = sy;pn.index = 0;vis[pn.x][pn.y] = true;path[cnt++] = pn;while (1){//找出队列中未访问的第一个元素PathNode node = path[idx++];//搜索四个方向,形成下一步可以通过的坐标for (int j = 0; j < 4; j++){int newx = node.x + dir[j].xstep;int newy = node.y + dir[j].ystep;//如果下一步坐标合法,未被访问且可以通过if (validate(newx, newy) && !vis[newx][newy] && maze[newx][newy] == 0){//生成新的结点PathNode pn;pn.x = newx;pn.y = newy;pn.parent_idx = node.index;pn.index = cnt;//如果为新的结点为出口,确定路径并返回if (newx == ex && newy == ey){identifyPath(pn);return;}//将新的结点放入路径数组中path[cnt++] = pn;//设置该结点已被访问过vis[newx][newy] = true;}}//如果遍历完所有的结点都没有找到出口,说明没有路径if (idx == cnt){cout << "no solution" << endl;break;}}
}int main()
{findShortestPath(0, 0, ROW - 1, COL - 1);return 0;
}
相关文章:
迷宫最短路径求解--c++
【代码】 #include<iostream> #include<queue> #include<stack> using namespace std; #define ROW 8 #define COL 8 //测试迷宫数据 int maze[ROW][COL] {{0,0,0,1,0,0,0,0},{0,1,0,1,0,1,0,1},{0,1,0,0,0,1,0,1},{0,1,0,1,1,1,0,1},{0,1,0,1,1,0,0,0},{0…...
SpringFramework总结
一.SpringFramework介绍 (一)Spring 广义上的 Spring 泛指以 Spring Framework 为基础的 Spring 技术栈。 Spring 已经不再是一个单纯的应用框架,而是逐渐发展成为一个由多个不同子项目(模块)组成的成熟技术,例如 Spring Frame…...
品牌与产品:消费者决策的经济逻辑与品牌宣传的战略意义
在当今日益全球化的经济环境中,品牌与产品之间的关系对于企业的成功与否起着至关重要的作用。然而,在消费者做出购买决策时,他们到底是在选择产品本身,还是在选择附着在产品之上的品牌价值?同样,当客户选择…...
MFC四种方法编写多线程
本文以四个demo为例,对MFC的多线程进行学习。学习的过程中写了四个demo,将其做成笔记,发布在csdn上面。 mfc多线程demo1 volatile BOOL m_bRun; CEdit* edit; void ThreadFunc(){CTime time;CString strTime;m_bRun true;while(m_bRun){ti…...
VPN简介
一、VPN 概念定义 VPN,即虚拟专用网络(Virtual Private Network),依靠ISP(Internet Service Provider)和NSP(Network Service Provider)在公共网络中建立的虚拟专用通信网络&#x…...
【C/C++】用C语言写一个数据仓库,存储和修改数据
这个代码实现了一个简单的数据仓库,其中数据被存储在一个3x3的二维数组中。用户可以通过控制台界面与这个数据仓库进行交互,可以选择查看数据或者修改数据。 基础版源码: #include <stdio.h>#define HOUSESIZE 3 int arr[HOUSESIZE][…...
YOLO v5与YOLO v8框图比较
1. 介绍 YOLO (You Only Look Once) 是一个用于目标检测的卷积神经网络模型,以其高精度、高速度和易用性著称。YOLO v5 是目前最流行的 YOLO 版本之一,而 YOLO v8 是 YOLO 的最新版本。 2. 原理详解 YOLO 系列模型的基本原理是将目标检测任务转化为图…...
Redis集群(5)
集群原理 节点通信 通信流程 在分布式存储系统中,维护节点元数据(如节点负责的数据、节点的故障状态等)是关键任务。常见的元数据维护方式分为集中式和P2P方式。Redis集群采用P2P的Gossip协议,这种协议的工作原理是节点之间不断…...
STM32H5 DAC 配置
STM32 H5 DAC的详细初始化过程可以分为以下几个步骤,以下是根据参考文章和相关资料整理的具体步骤和参数设置: 1、使能相关时钟: 使能GPIOA(或其他对应DAC输出引脚的GPIO端口)的时钟。这通常是通过调用RCC_APB2Perip…...
第十九节:暴力递归到动态规划
一 动画规划的概念 优化出现重复解的递归 一旦写出递归来,改动态规划就很快 尝试策略和状态转移方程是一码事 学会尝试是攻克动态规划最本质的能力 如果你发现你有重复调用的过程,动态规划在算过一次之后把答案记下来,下回在越到重复调用过程…...
服务器部署spring项目jar包使用bat文件,省略每次输入java -jar了
echo off set pathC:\Program Files\Java\jre1.8.0_191\bin START "YiXiangZhengHe-8516" "%path%/java" -Xdebug -jar -Dspring.profiles.activeprod -Dserver.port8516 YiXiangZhengHe-0.0.1-SNAPSHOT.jar 将set path后面改成jre的bin文件夹 START 后…...
2024备忘知识点
1. adb shell dumpsys package f |grep fin 过滤查找指纹服务 1. adsp write /sys/kernel/boot_adsp/boot 1 Please change replace dev_dbg into dev_err in kernel file adsp-loader.c. Then check whether "write /sys/kernel/boot_adsp/…...
JS基础与高级应用: 性能优化
在现代Web开发中,性能优化已成为前端工程师必须掌握的核心技能之一。本文从URL输入到页面加载完成的全过程出发,深入分析了HTTP协议的演进、域名解析、代码层面性能优化以及编译与渲染的最佳实践。通过节流、防抖、重复请求合并等具体技术手段࿰…...
Python | Leetcode Python题解之第145题二叉树的后序遍历
题目: 题解: class Solution:def postorderTraversal(self, root: TreeNode) -> List[int]:def addPath(node: TreeNode):count 0while node:count 1res.append(node.val)node node.righti, j len(res) - count, len(res) - 1while i < j:res…...
公司面试题总结(二)
7. 说说 JavaScript 中的数据类型?存储上的差别? • 基本类型: o Number o String o Boolean o Undefined o null o symbol • 引用类型 o Object o Array o Function • 声明变量时不同的内存地址分配: o 简单类型的…...
人脸识别和 ArcFace:用于深度人脸识别的附加角边际损失
在本文中,您将发现一种 ArcFace 方法,该方法可获得用于人脸识别的高分辨特征。阅读本文后,你将了解: 人脸识别任务如何工作。如何计算人脸匹配。SoftMax 和 ArcFace 的直观区别。ArcFace 的几何解释。ArcFace 背后的数学原理本文假定您已经熟悉用于多类分类、检测和 SoftMax…...
双标引领:汽车软件安全的ASPICE与ISO21434之道
随着汽车行业的飞速发展,尤其是智能化、网联化趋势的加剧,汽车软件开发的复杂性和安全性需求日益提升。在这样的背景下,ASPICE标准和ISO21434安全标准应运而生,为汽车软件的开发和管理提供了坚实的支撑。 ASPICE(Auto…...
再度牵手,制造升级 | 毅达科技IMS OS+通用产品集+行业套件项目正式启动!
在数字化与智能制造的浪潮中,制造业企业纷纷加快转型步伐,力求通过技术创新实现生产效率与质量的双重提升。近日,广东毅达医疗科技股份有限公司(以下简称“毅达科技”)再次携手盘古信息,正式启动了IMS 数字…...
大疆智图_空三二维重建成果传输
一、软件环境 1.1 所需软件 1、 大疆智图:点击下载; 2、 ArcGIS Pro 3.1.5:点击下载,建议使用IDM或Aria2等多线程下载器; 3、 IDM下载器:点击下载,或自行搜索; 4、 Fas…...
python实现无人机航拍图片像素坐标转世界坐标
背景 已知相机参数(传感器宽度和高度、图像宽度和高度、焦距、相对航高、像主点坐标 ),在给定像素坐标的前提下,求世界坐标,大部分通过AI来实现,不知道哪个步骤有问题,望大家指正 脚本 impor…...
【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型
摘要 拍照搜题系统采用“三层管道(多模态 OCR → 语义检索 → 答案渲染)、两级检索(倒排 BM25 向量 HNSW)并以大语言模型兜底”的整体框架: 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后,分别用…...
Debian系统简介
目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版ÿ…...
macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用
文章目录 问题现象问题原因解决办法 问题现象 macOS启动台(Launchpad)多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显,都是Google家的办公全家桶。这些应用并不是通过独立安装的…...
江苏艾立泰跨国资源接力:废料变黄金的绿色供应链革命
在华东塑料包装行业面临限塑令深度调整的背景下,江苏艾立泰以一场跨国资源接力的创新实践,重新定义了绿色供应链的边界。 跨国回收网络:废料变黄金的全球棋局 艾立泰在欧洲、东南亚建立再生塑料回收点,将海外废弃包装箱通过标准…...
C++ 基础特性深度解析
目录 引言 一、命名空间(namespace) C 中的命名空间 与 C 语言的对比 二、缺省参数 C 中的缺省参数 与 C 语言的对比 三、引用(reference) C 中的引用 与 C 语言的对比 四、inline(内联函数…...
如何为服务器生成TLS证书
TLS(Transport Layer Security)证书是确保网络通信安全的重要手段,它通过加密技术保护传输的数据不被窃听和篡改。在服务器上配置TLS证书,可以使用户通过HTTPS协议安全地访问您的网站。本文将详细介绍如何在服务器上生成一个TLS证…...
sqlserver 根据指定字符 解析拼接字符串
DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...
JVM虚拟机:内存结构、垃圾回收、性能优化
1、JVM虚拟机的简介 Java 虚拟机(Java Virtual Machine 简称:JVM)是运行所有 Java 程序的抽象计算机,是 Java 语言的运行环境,实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息,使得 Java 程序只需生成在 JVM 上运行的目标代码(字节码),就可以…...
华为OD机考-机房布局
import java.util.*;public class DemoTest5 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseSystem.out.println(solve(in.nextLine()));}}priv…...
GitHub 趋势日报 (2025年06月06日)
📊 由 TrendForge 系统生成 | 🌐 https://trendforge.devlive.org/ 🌐 本日报中的项目描述已自动翻译为中文 📈 今日获星趋势图 今日获星趋势图 590 cognee 551 onlook 399 project-based-learning 348 build-your-own-x 320 ne…...
