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.再探迷宫游戏 前面我们已经接触过了迷宫游戏,并且学会了如何使用 DFS 来解决迷宫最短路问题。用 DFS 求解迷宫最短路有一个很大的缺点,需要枚举所有可能的路径,读入的地图一旦很大,可能的搜索方案…...
【Spring原理进阶】SpringMVC调用链+JSP模板应用讲解
🎉🎉欢迎光临🎉🎉 🏅我是苏泽,一位对技术充满热情的探索者和分享者。🚀🚀 🌟特别推荐给大家我的最新专栏《Spring 狂野之旅:底层原理高级进阶》 🚀…...
23种计模式之Python/Go实现
目录 设计模式what?why?设计模式:设计模式也衍生出了很多的新的种类,不局限于这23种创建类设计模式(5种)结构类设计模式(7种)行为类设计模式(11种) 六大设计原则开闭原则里氏替换原…...
Qt可视化大屏布局
科技大屏现在非常流行,这里分享一下某个项目的大屏布局(忘了源码是哪个博主的了) 展示 这个界面整体是垂直布局,分为两个部分,标题是一个部分,然后下面的整体是一个layout布局,为另外一部分。 l…...
re:从0开始的CSS之旅 14. 显示模式的切换
1. 两个属性 display 属性可以用于转换元素的显示模式 可选值: block 转换为块元素 inline 转换为行内元素 inline-block 转换为行内块元素 none 不显示元素,并且不占用元素的位置 visibility 属性用于设置元素是否显示 可选值: visible 显示…...
K8S系列文章之 [Alpine基础环境配置]
用户手册:Alpine User Handbook 官方WIKI:Alpine Linux WIKI 安装 安装的实际逻辑是通过 setup-alpine 脚本去调用其他功能的脚本进行配置,可以通过 vi 查看脚本。如果某个部分安装失败,可退出后单独再次执行。通过镜像文件&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中最重要的日志之一,它记录了当mysql启动和停止时,以及服务器在运行过程中发生任何严重错误时的相关性息。当数据库出现任何故障导致无法正常使用时,建议首先查看此日志。 该日志是默认开启的…...
Waymo数据集下载与使用
在撰写论文时,接触到一个自动驾驶数据集Waymo Dataset 论文链接为:https://arxiv.org/abs/1912.04838v7 项目链接为:https://github.com/waymo-research/waymo-open-dataset 数据集链接为:https://waymo.com/open waymo提供了两种…...
蓝桥杯每日一题----素数筛
素数筛 素数筛的作用是筛选出[2,N]范围内的所有素数,本次主要讲解两种方法,分别是埃氏筛和欧拉筛。证明时会提到唯一分解定理,如果不知道的小伙伴可以先去学一学,那我们开始啦! 1.埃氏筛 主要思想:当找到…...
20240212请问如何将B站下载的软字幕转换成为SRT格式?
20240212请问如何将B站下载的软字幕转换成为SRT格式? 2024/2/12 12:47 百度搜索:字幕 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 变量进行设计:魔法配方的调配6.1.1 基础知识6.1.2 重点案例:创建可定制的主题6.1.3 拓展案例 1:响应式字体大小6.1.4 拓展案例 2:使用 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地址//定义信号处理函数,用于回收僵尸进程 void handler(int signo) {if(signo S…...
详解结构体内存对齐及结构体如何实现位段~
目录 编辑 一:结构体内存对齐 1.1对齐规则 1.2.为什么存在内存对齐 1.3修改默认对齐数 二.结构体实现位段 2.1什么是位段 2.2位段的内存分配 2.3位段的跨平台问题 2.4位段的应用 2.5位段使用的注意事项 三.完结散花 悟已往之不谏,知来者犹可…...
Linux网络编程——tcp套接字
文章目录 主要代码关于构造listen监听accepttelnet测试读取信息掉线重连翻译服务器演示 本章Gitee仓库:tcp套接字 主要代码 客户端: #pragma once#include"Log.hpp"#include<iostream> #include<cstring>#include<sys/wait.h…...
【计算机网络】协议层次及其服务模型
协议栈(protocol stack) 物理层链路层网络层运输层应用层我们自顶向下,所以从应用层开始探究应用层 协议 HTTP 提供了WEB文档的请求和传送SMTP 提供电子邮件报文的传输FTP 提供两个端系统之间的文件传输报文(message)是…...
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 解构赋值
搬运:JavaScript系列之解构赋值_js解构赋值-CSDN博客...
Vivado用ILA抓波形保存为CSV文件
将ILA观察到的波形数据捕获为CSV文件,抓10次,把文件合并,把源文件删除 运行方法: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期间被攻击的窘境
在红蓝攻防演练(hw行动)中,AD域若被攻击成功,是其中一个扣分最多的一项内容。每年,宁盾都会接到大量AD在hw期间被攻击,甚至是被打穿的企业客户。过去,企业还会借助2FA双因子认证加强OA、Exchang…...
OpenLayers 可视化之热力图
注:当前使用的是 ol 5.3.0 版本,天地图使用的key请到天地图官网申请,并替换为自己的key 热力图(Heatmap)又叫热点图,是一种通过特殊高亮显示事物密度分布、变化趋势的数据可视化技术。采用颜色的深浅来显示…...
Java 语言特性(面试系列1)
一、面向对象编程 1. 封装(Encapsulation) 定义:将数据(属性)和操作数据的方法绑定在一起,通过访问控制符(private、protected、public)隐藏内部实现细节。示例: public …...
Go 语言接口详解
Go 语言接口详解 核心概念 接口定义 在 Go 语言中,接口是一种抽象类型,它定义了一组方法的集合: // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的: // 矩形结构体…...
【第二十一章 SDIO接口(SDIO)】
第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...
Java多线程实现之Callable接口深度解析
Java多线程实现之Callable接口深度解析 一、Callable接口概述1.1 接口定义1.2 与Runnable接口的对比1.3 Future接口与FutureTask类 二、Callable接口的基本使用方法2.1 传统方式实现Callable接口2.2 使用Lambda表达式简化Callable实现2.3 使用FutureTask类执行Callable任务 三、…...
【Web 进阶篇】优雅的接口设计:统一响应、全局异常处理与参数校验
系列回顾: 在上一篇中,我们成功地为应用集成了数据库,并使用 Spring Data JPA 实现了基本的 CRUD API。我们的应用现在能“记忆”数据了!但是,如果你仔细审视那些 API,会发现它们还很“粗糙”:有…...
c#开发AI模型对话
AI模型 前面已经介绍了一般AI模型本地部署,直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型,但是目前国内可能使用不多,至少实践例子很少看见。开发训练模型就不介绍了&am…...
算法笔记2
1.字符串拼接最好用StringBuilder,不用String 2.创建List<>类型的数组并创建内存 List arr[] new ArrayList[26]; Arrays.setAll(arr, i -> new ArrayList<>()); 3.去掉首尾空格...
MacOS下Homebrew国内镜像加速指南(2025最新国内镜像加速)
macos brew国内镜像加速方法 brew install 加速formula.jws.json下载慢加速 🍺 最新版brew安装慢到怀疑人生?别怕,教你轻松起飞! 最近Homebrew更新至最新版,每次执行 brew 命令时都会自动从官方地址 https://formulae.…...
深入理解Optional:处理空指针异常
1. 使用Optional处理可能为空的集合 在Java开发中,集合判空是一个常见但容易出错的场景。传统方式虽然可行,但存在一些潜在问题: // 传统判空方式 if (!CollectionUtils.isEmpty(userInfoList)) {for (UserInfo userInfo : userInfoList) {…...
