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

变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析

一、变量声明设计&#xff1a;let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性&#xff0c;这种设计体现了语言的核心哲学。以下是深度解析&#xff1a; 1.1 设计理念剖析 安全优先原则&#xff1a;默认不可变强制开发者明确声明意图 let x 5; …...

中南大学无人机智能体的全面评估!BEDI:用于评估无人机上具身智能体的综合性基准测试

作者&#xff1a;Mingning Guo, Mengwei Wu, Jiarun He, Shaoxian Li, Haifeng Li, Chao Tao单位&#xff1a;中南大学地球科学与信息物理学院论文标题&#xff1a;BEDI: A Comprehensive Benchmark for Evaluating Embodied Agents on UAVs论文链接&#xff1a;https://arxiv.…...

Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件

今天呢&#xff0c;博主的学习进度也是步入了Java Mybatis 框架&#xff0c;目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学&#xff0c;希望能对大家有所帮助&#xff0c;也特别欢迎大家指点不足之处&#xff0c;小生很乐意接受正确的建议&…...

理解 MCP 工作流:使用 Ollama 和 LangChain 构建本地 MCP 客户端

&#x1f31f; 什么是 MCP&#xff1f; 模型控制协议 (MCP) 是一种创新的协议&#xff0c;旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议&#xff0c;它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...

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

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

NXP S32K146 T-Box 携手 SD NAND(贴片式TF卡):驱动汽车智能革新的黄金组合

在汽车智能化的汹涌浪潮中&#xff0c;车辆不再仅仅是传统的交通工具&#xff0c;而是逐步演变为高度智能的移动终端。这一转变的核心支撑&#xff0c;来自于车内关键技术的深度融合与协同创新。车载远程信息处理盒&#xff08;T-Box&#xff09;方案&#xff1a;NXP S32K146 与…...

C/C++ 中附加包含目录、附加库目录与附加依赖项详解

在 C/C 编程的编译和链接过程中&#xff0c;附加包含目录、附加库目录和附加依赖项是三个至关重要的设置&#xff0c;它们相互配合&#xff0c;确保程序能够正确引用外部资源并顺利构建。虽然在学习过程中&#xff0c;这些概念容易让人混淆&#xff0c;但深入理解它们的作用和联…...

[免费]微信小程序问卷调查系统(SpringBoot后端+Vue管理端)【论文+源码+SQL脚本】

大家好&#xff0c;我是java1234_小锋老师&#xff0c;看到一个不错的微信小程序问卷调查系统(SpringBoot后端Vue管理端)【论文源码SQL脚本】&#xff0c;分享下哈。 项目视频演示 【免费】微信小程序问卷调查系统(SpringBoot后端Vue管理端) Java毕业设计_哔哩哔哩_bilibili 项…...

Web中间件--tomcat学习

Web中间件–tomcat Java虚拟机详解 什么是JAVA虚拟机 Java虚拟机是一个抽象的计算机&#xff0c;它可以执行Java字节码。Java虚拟机是Java平台的一部分&#xff0c;Java平台由Java语言、Java API和Java虚拟机组成。Java虚拟机的主要作用是将Java字节码转换为机器代码&#x…...

Spring Security 认证流程——补充

一、认证流程概述 Spring Security 的认证流程基于 过滤器链&#xff08;Filter Chain&#xff09;&#xff0c;核心组件包括 UsernamePasswordAuthenticationFilter、AuthenticationManager、UserDetailsService 等。整个流程可分为以下步骤&#xff1a; 用户提交登录请求拦…...