迷宫最短路径求解--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;
}

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

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

相关文章

Fiddler抓包工具详细使用教程

各位做测试的同学想必对抓包工具fiddler并不陌生&#xff0c;但是很多同学可能没有总结过它的用法&#xff0c;下面我总结了fiddler一些常用的用法。 Web端抓包配置 打开Fiddler&#xff0c;Tools -> Fiddler Options -> HTTPS 配置完后记得要重启Fiddler 选中Decrpt …

34.打印K型

上海市计算机学会竞赛平台 | YACSYACS 是由上海市计算机学会于2019年发起的活动,旨在激发青少年对学习人工智能与算法设计的热情与兴趣,提升青少年科学素养,引导青少年投身创新发现和科研实践活动。https://www.iai.sh.cn/problem/76 题目描述 小爱想用 * 打出一个大写的 K。…

6.11 作业

以下是一个简单的比喻&#xff0c;将多态概念与生活中的实际情况相联系&#xff1a; 比喻&#xff1a;动物园的讲解员和动物表演 想象一下你去了一家动物园&#xff0c;看到了许多不同种类的动物&#xff0c;如狮子、大象、猴子等。现在&#xff0c;动物园里有一位讲解员&…

使用fvm切换flutter版本

切换flutter版本 下载fvm 1、dart pub global activate fvm dart下载fvm 2、warning中获取下载本地的地址 3、添加用户变量path&#xff1a; 下载地址 终端查看fvm版本 fvm --version 4、指定fvm文件缓存地址 fvm config --cache-path C:\src\fvm&#xff08;自定义地址&…

《精通ChatGPT:从入门到大师的Prompt指南》附录A:常用Prompt示例

附录A&#xff1a;常用Prompt示例 在《精通ChatGPT&#xff1a;从入门到大师的Prompt指南》的附录A中&#xff0c;我们将展示一系列常用的Prompt示例&#xff0c;帮助读者更好地理解和应用Prompt技术。每个示例将包含Prompt的描述、使用场景、预期结果以及实际输出。希望这些示…

调试环境搭建(Redis 6.X 版本)

今儿&#xff0c;我们来搭建一个 Redis 调试环境&#xff0c;目标是&#xff1a; 启动 Redis Server &#xff0c;成功断点调试 Server 的启动过程。使用 redis-cli 启动一个 Client 连接上 Server&#xff0c;并使用 get key 指令&#xff0c;发起一次 key 的读取。 视频可见…

公司面试题总结(二)

7. 说说 JavaScript 中的数据类型&#xff1f;存储上的差别&#xff1f; • 基本类型&#xff1a; o Number o String o Boolean o Undefined o null o symbol • 引用类型 o Object o Array o Function • 声明变量时不同的内存地址分配&#xff1a; o 简单类型的…

Excel最基本的常用函数

最基本最常用的函数&#xff0c;掌握了可以解决大部分问题。 (笔记模板由python脚本于2024年06月11日 19:05:56创建&#xff0c;本篇笔记适合熟悉excel的coder翻阅) 【学习的细节是欢悦的历程】 Python 官网&#xff1a;https://www.python.org/ Free&#xff1a;大咖免费“圣…

小白学RAG:大模型 RAG 技术实践总结

节前&#xff0c;我们组织了一场算法岗技术&面试讨论会&#xff0c;邀请了一些互联网大厂朋友、今年参加社招和校招面试的同学。 针对大模型技术趋势、大模型落地项目经验分享、新手如何入门算法岗、该如何准备面试攻略、面试常考点等热门话题进行了深入的讨论。 汇总合集…

【设计模式】行为型设计模式之 策略模式学习实践

介绍 策略模式&#xff08;Strategy&#xff09;&#xff0c;就是⼀个问题有多种解决⽅案&#xff0c;选择其中的⼀种使⽤&#xff0c;这种情况下我们 使⽤策略模式来实现灵活地选择&#xff0c;也能够⽅便地增加新的解决⽅案。⽐如做数学题&#xff0c;⼀个问题的 解法可能有…

【STM32】基于I2C协议的OLED显示(利用U82G库)

【STM32】基于I2C协议的OLED显示(利用U82G库) 文章目录 【STM32】基于I2C协议的OLED显示(利用U82G库)一、实验背景二、U8g2介绍&#xff08;一&#xff09;获取&#xff08;二&#xff09;简介 三、实践&#xff08;一&#xff09;CubexMX配置&#xff08;二&#xff09;U8g2配…

SPSS 27.0.1 IF026 软件安装教程

软件介绍 SPSS是一款统计产品与服务解决方案的软件&#xff0c;最初软件全称为“社会科学统计软件包”(SolutionsStatistical Package for the Social Sciences) 下载链接 https://pan.quark.cn/s/fb683999be3e 安装步骤 1、双击运行点击解压 2、进入解压后文件 3、右键管…

流批一体计算引擎-9-[Flink]中的数量窗与时间窗

1 数量窗 1.1 数量滚动窗口 0基础学习PyFlink——个数滚动窗口(Tumbling Count Windows) 1.1.1 代码分析 Tumbling Count Windows是指按元素个数计数的滚动窗口。 滚动窗口是指没有元素重叠的窗口。 (1)构造了一个KeyedStream&#xff0c;用于存储word_count_data中的数据。…

铸铁机械5G智能工厂工业物联数字孪生平台,推进制造业数字化转型

铸铁机械5G智能工厂工业物联数字孪生平台&#xff0c;推进制造业数字化转型。工业物联数字孪生平台以5G技术为基础&#xff0c;通过工业物联网连接铸铁机械生产过程中的各个环节&#xff0c;运用数字孪生技术构建虚拟工厂&#xff0c;实现生产过程的实时监测、模拟与优化&#…

【因果推断python】28_面板数据和固定效应2

目录 固定效应 固定效应 为了方面后面更正式地讲述&#xff0c;让我们首先看一下我们拥有的数据。按照我们的例子&#xff0c;我们将尝试估计婚姻对收入的影响。我们的数据包含多年以来多个个体 (nr) 的这两个变量&#xff0c;married 和lwage。请注意&#xff0c;工资采用对数…

java之IO流和集合框架的笔记

1 File类的使用 1.1 概述 File类及本章下的各种流&#xff0c;都定义在java.io包下。 一个File对象代表硬盘或网络中可能存在的一个文件或者文件目录&#xff08;俗称文件夹&#xff09;&#xff0c;与平台无关。&#xff08;体会万事万物皆对象&#xff09; File 能新建、删…

10_Transformer预热---注意力机制(Attention)

1.1 什么是注意力机制(attention) 注意力机制&#xff08;Attention Mechanism&#xff09;是一种在神经网络中用于增强模型处理特定输入特征的能力的技术。它最早被应用于自然语言处理&#xff08;NLP&#xff09;任务中&#xff0c;特别是在机器翻译中&#xff0c;如Google的…

Shell脚本和变量

文章目录 Shell脚本shell的解释器Shell的作用Shell脚本的构成Shell的执行方式 重定向操作变量变量的类型&#xff1a;变量名的规范变量值的规范整数运算 &#xff0b; &#xff0d; / %小数运算 小数运算 Shell脚本 脚本就是可运行的代码的集合&#xff0c;脚本语言&#xff…

hadoop_概念

前言&#xff1a; 本篇文章仅用于个人学习笔记&#xff0c;仅限于参考&#xff0c;内容如有侵权&#xff0c;请联系删除&#xff0c;谢谢&#xff01; 一&#xff1a;大数据简介 大数据概念 : 指无法在一定时间范围内用常规软件工具进行捕管理和处理的数据集合&#xff0c;…

30岁迷茫?AI赛道,人生新起点

前言 30岁&#xff0c;对于许多人来说&#xff0c;是一个人生的分水岭。在这个年纪&#xff0c;有些人可能已经在某个领域取得了不小的成就&#xff0c;而有些人则可能开始对未来的职业方向感到迷茫。如果你正处于这个阶段&#xff0c;那么你可能会问自己&#xff1a;30岁转行…