C++ bfs再探迷宫游戏(五十五)【第二篇】

今天我们用bfs解决迷宫游戏。

1.再探迷宫游戏

前面我们已经接触过了迷宫游戏,并且学会了如何使用 DFS 来解决迷宫最短路问题。用 DFS 求解迷宫最短路有一个很大的缺点,需要枚举所有可能的路径,读入的地图一旦很大,可能的搜索方案数量会非常多,用 DFS 搜索显然效率会很低。

我们可以借助 BFS 来求解迷宫游戏。由于 BFS 是分层搜索,因此,第一次搜索到终点的时候,当前搜索的层数就是最短路径的长度。

图片

如果我们要求解起点到某个点的最短距离时,可以设置 int dis[maxn][maxn]; 记录起点到达每个点的最短距离。因为 bfs 搜索过程中第一次搜索到终点的时候是最短距离,所以可以让 dis 数组初始化为 −1−1,搜索过程中如果刚搜索到的点的 dis 等于 −1−1,表示这个点是第一次搜索到的点,需要更新 dis 数组。

程序:

#include <iostream>
#include <string>
#include <queue>
using namespace std;
int n, m;
string maze[110];
bool vis[110][110];
int dir[4][2] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
bool in(int x, int y) {return 0 <= x && x < n && 0 <= y && y < m;
}
struct node {int x, y, d;node (int _x, int _y, int _d) {x = _x;y = _y;d = _d;}
};
int bfs (int sx, int sy){//从起点开始搜索queue <node> q;q.push(node (sx, sy, 0));vis[sx][sy] = true;//开始标记while (!q.empty()) {node now = q.front();//取出状态q.pop();//删除状态if (maze[now.x][now.y] == 'T') {return now.d;}for (int i = 0; i < 4; i++) {int tx = now.x + dir[i][0];int ty = now.y + dir[i][1];//横纵变化if (in(tx, ty) && maze[tx][ty] != '*' && !vis[tx][ty]) {//合法性判断vis[tx][ty] = true;q.push(node(tx, ty, now.d + 1));}}}return -1; //搜索失败
}
int main() {cin >> n >> m;for (int i = 0; i < n; i++) {cin >> maze[i];}int x, y;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (maze[i][j] == 'S') {x = i;y = j;}}}cout << bfs(x, y) << endl;return 0;
}

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

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

相关文章

安全之护网(HVV)、红蓝对抗

文章目录 红蓝对抗什么是护网行动&#xff1f;护网分类护网的时间 什么是红蓝对抗红蓝对抗演练的目的什么是企业红蓝对抗红蓝对抗价值参考 红蓝对抗 什么是护网行动&#xff1f; 护网的定义是以国家组织组织事业单位、国企单位、名企单位等开展攻防两方的网络安全演习。进攻方…

Vue--》深入学习Tailwind CSS掌握优雅而高效的前端样式开发

Tailwind CSS是一个非常强大且灵活的CSS框架&#xff0c;适用于开发者希望高度定制化界面样式的项目。今天博主就 Tailwind CSS 做一个简单介绍以及案例讲解&#xff0c;争取读者阅读文章后入门。 仅靠一篇文章博主也不可能将Tailwind CSS所有内容讲解的面面俱到&#xff0c;在…

购物|电商购物小程序|基于微信小程序的购物系统设计与实现(源码+数据库+文档)

电商购物小程序目录 目录 基于微信小程序的购物系统设计与实现 一、前言 二、系统功能设计 三、系统实现 1、用户前台功能实现 2、管理员后台功能实现 四、数据库设计 1、实体ER图 2、具体的表设计如下所示&#xff1a; 五、核心代码 六、论文参考 七、最新计算机毕设…

【力扣】5.最长回文子串

这道题我主要是通过动态规划来进行解题&#xff0c;看了我好久&#xff08;解析&#xff09;&#xff0c;生疏了呀。 首先就是判断一个字符串是不是回文&#xff0c;我们可以设置两个指针&#xff0c;从前往后进行判断即可&#xff0c;运用暴力解题法&#xff0c;这里运用的动…

react【四】css

文章目录 1、css1.1 react和vue css的对比1.2 内联样式1.3 普通的css1.4 css modules1.5 在react中使用less1.6 CSS in JS1.6.1 模板字符串的基本使用1.6.2 styled-components的基本使用1.6.3 接受传参1.6.4 使用变量1.6.5 继承样式 避免代码冗余1.6.6 设置主题色 1.7 React中添…

Redis篇之redis是单线程

一、redis是单线程 Redis是单线程的&#xff0c;但是为什么还那么快&#xff1f;主要原因有下面3点原因&#xff1a; 1. Redis是纯内存操作&#xff0c;执行速度非常快。 2. 采用单线程&#xff0c;避免不必要的上下文切换可竞争条件&#xff0c;多线程还要考虑线程安全问题。 …

【电路笔记】-串联电感

串联电感 文章目录 串联电感1、概述2、电感串联示例13、互耦串联电感器4、电感串联示例25、电感串联示例36、总结当电感器以菊花链方式连接在一起并共享公共电流时,它们可以串联连接在一起。 1、概述 这些电感器的互连产生了更复杂的网络,其总电感是各个电感器的组合。 然而…

CSS Selector—选择方法,和html自动——异步社区的爬取(动态网页)——爬虫(get和post的区别)

这里先说一下GET请求和POST请求&#xff1a; post我们平时是要加data的也就是信息&#xff0c;你会发现我们平时百度之类的 搜索都是post请求 get我们带的是params&#xff0c;是发送我们指定的内容。 要注意是get和post请求&#xff01;&#xff01;&#xff01; 先说一下异…

Linux_进程概念

硬件系统 软件系统 进程概念 进程状态 孤儿进程 进程优先级 一.硬件系统 1.1 冯诺依曼体系结构 数学家冯诺依曼提出了计算机制造的三个基本原则&#xff0c;即采用二进制逻辑、程序存储执行以及计算机由五个部分组成&#xff08;运算器、控制器、存储器、输入设备、输出设备&a…

[Doris] Doris的安装和部署 (二)

文章目录 1.安装要求1.1 Linux操作系统要求1.2 软件需求1.3 注意事项1.4 内部端口 2.集群部署2.1 操作系统安装要求2.2 下载安装包2.3 解压2.4 配置FE2.5 配置BE2.6 添加BE2.7 FE 扩容和缩容2.8 Doris 集群群起脚本 3.图形化 1.安装要求 1.1 Linux操作系统要求 1.2 软件需求 1…

用EXCEL从地址(上海)中提取各区(浦东新区等区)信息

背景&#xff1a; 朋友工作需要经常用EXCEL把各上海用户收货地址中的区提取出来&#xff0c;之前一直手动处理&#xff0c;希望我帮忙用EXCEL公式直接提取处理。 数据样式&#xff1a; 中国上海市浦东新区A小区 上海徐汇区B小区 中国&#xff0c;上海&#xff0c;浦东新区&a…

JVM相关-JVM模型、垃圾回收、JVM调优

一、JVM模型 JVM内部体型划分 JVM的内部体系结构分为三部分&#xff0c;分别是&#xff1a;类加载器&#xff08;ClassLoader&#xff09;子系统、运行时数据区&#xff08;内存&#xff09;和执行引擎 1、类加载器 概念 每个JVM都有一个类加载器子系统&#xff08;class l…

CSS之盒模型

盒模型概念 浏览器盒模型&#xff08;Box Model&#xff09;是CSS中的基本概念&#xff0c;它描述了元素在布局过程中如何占据空间。盒模型由内容&#xff08;content&#xff09;、内边距&#xff08;padding&#xff09;、边框&#xff08;border&#xff09;、和外边距&…

Java实现教学资源共享平台 JAVA+Vue+SpringBoot+MySQL

目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 数据中心模块2.2 课程档案模块2.3 课程资源模块2.4 课程作业模块2.5 课程评价模块 三、系统设计3.1 用例设计3.2 类图设计3.3 数据库设计3.3.1 课程档案表3.3.2 课程资源表3.3.3 课程作业表3.3.4 课程评价表 四、系统展…

MATLAB | 情人节画个花瓣venn图?

之前七夕节情人节各种花&#xff0c;相册&#xff0c;爱心啥的都快画够了&#xff0c;今年画个花瓣韦恩图&#xff1f; 花瓣上的数字是仅属于该类的样本数&#xff0c;而中心的数字是属于每一类的样本数 教程部分 0 数据准备 % 给组起名t1 t2 t3...t15 setName compose(t%d,…

交叉熵损失函数(Cross-Entropy Loss)的基本概念与程序代码

交叉熵损失函数&#xff08;Cross-Entropy Loss&#xff09;是机器学习和深度学习中常用的损失函数之一&#xff0c;用于分类问题。其基本概念如下&#xff1a; 1. 基本解释&#xff1a; 交叉熵损失函数衡量了模型预测的概率分布与真实概率分布之间的差异。在分类问题中&…

【Tauri】(1):使用Tauri1.5版本,进行桌面应用开发,在windows,linux进行桌面GUI应用程序开发,可以打包成功,使用 vite 最方便

1&#xff0c;视频地址&#xff1a; https://www.bilibili.com/video/BV1Pz421d7s4/ 【Tauri】&#xff08;1&#xff09;&#xff1a;使用Tauri1.5版本&#xff0c;进行桌面应用开发&#xff0c;在windows&#xff0c;linux进行桌面GUI应用程序开发&#xff0c;可以打包成功&…

【Qt】qt常用控件之QIcon 以及 qrc机制设置图片路径(QtCreator)

文章目录 1. QIcon / windowIcon2. setIcon() 与 setwindowIcon()2.1 setIcon() 介绍与使用2.2 setWindowIcon 介绍与使用 3. 路径问题 & qrc机制的引入3.1 绝对路径 / 相对路径 的问题3.2 qrc机制3.3 在QtCreator下利用qrc机制引入图片 1. QIcon / windowIcon QIcon QIco…

《SQLi-Labs》05. Less 29~37

title: 《SQLi-Labs》05. Less 29~37 date: 2024-01-17 22:49:10 updated: 2024-02-12 18:09:10 categories: WriteUp&#xff1a;Security-Lab excerpt: HTTP 参数污染&#xff0c;联合注入、宽字节注入。 comments: false tags: top_image: /images/backimg/SunsetClimbing.p…

限制资源使用

限制资源使用 您需要显示对服务器资源的访问来保护Web应用程序和应用程序数据不受未授权用户的访问。在Java EE Web应用程序中,您可以通过在应用服务器中创建用户和用户组来保护资源免受未经授权的访问。您可以为应用程序定义角色并在部署过程中将角色分配给用户。 1. 创建授权…