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

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;
}

相关文章:

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

今天我们用bfs解决迷宫游戏。 1.再探迷宫游戏 前面我们已经接触过了迷宫游戏&#xff0c;并且学会了如何使用 DFS 来解决迷宫最短路问题。用 DFS 求解迷宫最短路有一个很大的缺点&#xff0c;需要枚举所有可能的路径&#xff0c;读入的地图一旦很大&#xff0c;可能的搜索方案…...

【Spring原理进阶】SpringMVC调用链+JSP模板应用讲解

&#x1f389;&#x1f389;欢迎光临&#x1f389;&#x1f389; &#x1f3c5;我是苏泽&#xff0c;一位对技术充满热情的探索者和分享者。&#x1f680;&#x1f680; &#x1f31f;特别推荐给大家我的最新专栏《Spring 狂野之旅&#xff1a;底层原理高级进阶》 &#x1f680…...

23种计模式之Python/Go实现

目录 设计模式what?why?设计模式&#xff1a;设计模式也衍生出了很多的新的种类&#xff0c;不局限于这23种创建类设计模式&#xff08;5种&#xff09;结构类设计模式&#xff08;7种&#xff09;行为类设计模式&#xff08;11种&#xff09; 六大设计原则开闭原则里氏替换原…...

Qt可视化大屏布局

科技大屏现在非常流行&#xff0c;这里分享一下某个项目的大屏布局&#xff08;忘了源码是哪个博主的了&#xff09; 展示 这个界面整体是垂直布局&#xff0c;分为两个部分&#xff0c;标题是一个部分&#xff0c;然后下面的整体是一个layout布局&#xff0c;为另外一部分。 l…...

re:从0开始的CSS之旅 14. 显示模式的切换

1. 两个属性 display 属性可以用于转换元素的显示模式 可选值&#xff1a; block 转换为块元素 inline 转换为行内元素 inline-block 转换为行内块元素 none 不显示元素&#xff0c;并且不占用元素的位置 visibility 属性用于设置元素是否显示 可选值&#xff1a; visible 显示…...

K8S系列文章之 [Alpine基础环境配置]

用户手册&#xff1a;Alpine User Handbook 官方WIKI&#xff1a;Alpine Linux WIKI 安装 安装的实际逻辑是通过 setup-alpine​ 脚本去调用其他功能的脚本进行配置&#xff0c;可以通过 vi 查看脚本。如果某个部分安装失败&#xff0c;可退出后单独再次执行。通过镜像文件&a…...

单页404源码

<!doctype html> <html> <head> <meta charset"utf-8"> <title>简约 404错误页</title><link rel"shortcut icon" href"./favicon.png"><style> import url("https://fonts.googleapis.co…...

MySQL-运维

一、日志 1.错误日志 错误日志是MySQL中最重要的日志之一&#xff0c;它记录了当mysql启动和停止时&#xff0c;以及服务器在运行过程中发生任何严重错误时的相关性息。当数据库出现任何故障导致无法正常使用时&#xff0c;建议首先查看此日志。 该日志是默认开启的&#xf…...

Waymo数据集下载与使用

在撰写论文时&#xff0c;接触到一个自动驾驶数据集Waymo Dataset 论文链接为&#xff1a;https://arxiv.org/abs/1912.04838v7 项目链接为&#xff1a;https://github.com/waymo-research/waymo-open-dataset 数据集链接为&#xff1a;https://waymo.com/open waymo提供了两种…...

蓝桥杯每日一题----素数筛

素数筛 素数筛的作用是筛选出[2,N]范围内的所有素数&#xff0c;本次主要讲解两种方法&#xff0c;分别是埃氏筛和欧拉筛。证明时会提到唯一分解定理&#xff0c;如果不知道的小伙伴可以先去学一学&#xff0c;那我们开始啦&#xff01; 1.埃氏筛 主要思想&#xff1a;当找到…...

20240212请问如何将B站下载的软字幕转换成为SRT格式?

20240212请问如何将B站下载的软字幕转换成为SRT格式&#xff1f; 2024/2/12 12:47 百度搜索&#xff1a;字幕 json 转 srt json srt https://blog.csdn.net/a_wh_white/article/details/120687363?share_token2640663e-f468-4737-9b55-73c808f5dcf0 https://blog.csdn.net/a_w…...

《CSS 简易速速上手小册》第6章:高级 CSS 技巧(2024 最新版)

文章目录 6.1 使用 CSS 变量进行设计&#xff1a;魔法配方的调配6.1.1 基础知识6.1.2 重点案例&#xff1a;创建可定制的主题6.1.3 拓展案例 1&#xff1a;响应式字体大小6.1.4 拓展案例 2&#xff1a;使用 CSS 变量创建动态阴影效果 6.2 calc(), min(), max() 等函数的应用&am…...

2024-02-11 多进程、多线程 work

1. 创建一个多进程服务器和多线程服务器 a. 多进程 #include<myhead.h> #define PORT 9999 //端口号 #define IP "192.168.125.113" //IP地址//定义信号处理函数&#xff0c;用于回收僵尸进程 void handler(int signo) {if(signo S…...

详解结构体内存对齐及结构体如何实现位段~

目录 ​编辑 一&#xff1a;结构体内存对齐 1.1对齐规则 1.2.为什么存在内存对齐 1.3修改默认对齐数 二.结构体实现位段 2.1什么是位段 2.2位段的内存分配 2.3位段的跨平台问题 2.4位段的应用 2.5位段使用的注意事项 三.完结散花 悟已往之不谏&#xff0c;知来者犹可…...

Linux网络编程——tcp套接字

文章目录 主要代码关于构造listen监听accepttelnet测试读取信息掉线重连翻译服务器演示 本章Gitee仓库&#xff1a;tcp套接字 主要代码 客户端&#xff1a; #pragma once#include"Log.hpp"#include<iostream> #include<cstring>#include<sys/wait.h…...

【计算机网络】协议层次及其服务模型

协议栈&#xff08;protocol stack&#xff09; 物理层链路层网络层运输层应用层我们自顶向下&#xff0c;所以从应用层开始探究应用层 协议 HTTP 提供了WEB文档的请求和传送SMTP 提供电子邮件报文的传输FTP 提供两个端系统之间的文件传输报文&#xff08;message&#xff09;是…...

prometheus之redis_exporter部署

下载解压压缩包 mkdir /opt/redis_exporter/ cd /opt/redis_exporter/ wget http://soft.download/soft/linux/prometheus/redis_exporter/redis_exporter-v1.50.0.linux-amd64.tar.gz tar -zxvf redis_exporter-v1.50.0.linux-amd64.tar.gz ln -s /opt/redis_exporter/redis_…...

js 解构赋值

搬运&#xff1a;JavaScript系列之解构赋值_js解构赋值-CSDN博客...

Vivado用ILA抓波形保存为CSV文件

将ILA观察到的波形数据捕获为CSV文件&#xff0c;抓10次&#xff0c;把文件合并&#xff0c;把源文件删除 运行方法&#xff1a;Vivado的 Tcl console 窗口输入命令 set tcl_dir F:/KLD_FPGA/Code/sim set tcl_filename TCL_ILA_TRIG_V1.2.tcl source $tcl_dir/$tcl_filenam…...

微软AD域替代方案,助力企业摆脱hw期间被攻击的窘境

在红蓝攻防演练&#xff08;hw行动&#xff09;中&#xff0c;AD域若被攻击成功&#xff0c;是其中一个扣分最多的一项内容。每年&#xff0c;宁盾都会接到大量AD在hw期间被攻击&#xff0c;甚至是被打穿的企业客户。过去&#xff0c;企业还会借助2FA双因子认证加强OA、Exchang…...

深度学习在微纳光子学中的应用

深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向&#xff1a; 逆向设计 通过神经网络快速预测微纳结构的光学响应&#xff0c;替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...

【OSG学习笔记】Day 18: 碰撞检测与物理交互

物理引擎&#xff08;Physics Engine&#xff09; 物理引擎 是一种通过计算机模拟物理规律&#xff08;如力学、碰撞、重力、流体动力学等&#xff09;的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互&#xff0c;广泛应用于 游戏开发、动画制作、虚…...

DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径

目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...

基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容

基于 ​UniApp + WebSocket​实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配​微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...

【配置 YOLOX 用于按目录分类的图片数据集】

现在的图标点选越来越多&#xff0c;如何一步解决&#xff0c;采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集&#xff08;每个目录代表一个类别&#xff0c;目录下是该类别的所有图片&#xff09;&#xff0c;你需要进行以下配置步骤&#x…...

JDK 17 新特性

#JDK 17 新特性 /**************** 文本块 *****************/ python/scala中早就支持&#xff0c;不稀奇 String json “”" { “name”: “Java”, “version”: 17 } “”"; /**************** Switch 语句 -> 表达式 *****************/ 挺好的&#xff…...

3403. 从盒子中找出字典序最大的字符串 I

3403. 从盒子中找出字典序最大的字符串 I 题目链接&#xff1a;3403. 从盒子中找出字典序最大的字符串 I 代码如下&#xff1a; class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...

自然语言处理——循环神经网络

自然语言处理——循环神经网络 循环神经网络应用到基于机器学习的自然语言处理任务序列到类别同步的序列到序列模式异步的序列到序列模式 参数学习和长程依赖问题基于门控的循环神经网络门控循环单元&#xff08;GRU&#xff09;长短期记忆神经网络&#xff08;LSTM&#xff09…...

Element Plus 表单(el-form)中关于正整数输入的校验规则

目录 1 单个正整数输入1.1 模板1.2 校验规则 2 两个正整数输入&#xff08;联动&#xff09;2.1 模板2.2 校验规则2.3 CSS 1 单个正整数输入 1.1 模板 <el-formref"formRef":model"formData":rules"formRules"label-width"150px"…...

Java多线程实现之Thread类深度解析

Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...