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

广度优先(BFS)(例子:迷宫)

       广度优先搜索算法(BFS)是一种用于图形和树数据结构的搜索算法。该算法从根节点开始搜索,然后依次访问每个相邻节点。在搜索过程中,每个节点都标记为已访问,以避免重复访问。BFS算法适用于寻找最短路径的问题,因为它保证找到的解是距离根节点最近的解。

       BFS算法的基本思想是使用队列保存已经访问的节点。首先将根节点入队,然后从队列中取出一个节点进行访问,并将与该节点相邻的未访问节点入队。重复这个过程,直到队列为空为止。BFS算法的时间复杂度为O(V+E),其中V为节点数,E为边数。

#include<iostream>//广度搜索,迷宫例题
using namespace std;
typedef struct node
{int x;int y;int f;int s;
};
int main()
{node que[2501];int a[51][51] = { 0 };//储存地图int book[51][51] = { 0 };//标记是否走过int next[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };//右,下,左,上int head, tail;int x, y, q, p,n,m,tx,ty;cout << "输入地图规模:" << endl;cin >> n >> m;//输入地图规模for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)cin >> a[i][j];cout << "输入起点、终点:" << endl;cin >> x >> y >> q >> p;//输入起点,终点head = 1, tail = 1;que[tail].x = x;que[tail].y = y;que[tail].f = 0;que[tail].s = 0;tail++;book[x][y] = 1;int flag = 0;//标记是否到达终点while (head < tail){for (int k = 0; k < 4; k++){tx = que[head].x + next[k][0];ty = que[head].y + next[k][1];if (tx<1 || tx>n || ty < 1 || ty>n)continue;if (a[tx][ty] == 0 && book[tx][ty] == 0)//没有障碍物且没走过{book[tx][ty] = 1;//标记已经走过que[tail].x = tx;que[tail].y = ty;que[tail].f = head;que[tail].s = que[head].s + 1;tail++;}if (tx == q && ty == p){flag = 1;break;}}if (flag == 1)break;head++;}cout << que[tail - 1].s;
}

相关文章:

广度优先(BFS)(例子:迷宫)

广度优先搜索算法&#xff08;BFS&#xff09;是一种用于图形和树数据结构的搜索算法。该算法从根节点开始搜索&#xff0c;然后依次访问每个相邻节点。在搜索过程中&#xff0c;每个节点都标记为已访问&#xff0c;以避免重复访问。BFS算法适用于寻找最短路径的问题&#xff0…...

【安卓源码】安卓Watchdog 机制

在Android系统中&#xff0c;也设计了一个软件层面Watchdog&#xff0c;用于保护一些重要的系统服务&#xff0c;比如&#xff1a;AMS、WMS、PMS等&#xff0c;由于以上核心服务运行在system_server进程里面&#xff0c;所以当以上服务出现异常时&#xff0c;通常会将system_se…...

inscode连接不上gpu,持续8小时,为了数据不丢失续费了6小时,我只想知道什么时候可以连接

并且给我相应的补偿...

QT位置相关函数

Qt&#xff08;Qt Framework&#xff09;是一个流行的C应用程序开发框架&#xff0c;提供了丰富的位置相关函数和类&#xff0c;用于处理窗口、窗口小部件和图形的位置和几何操作。以下是一些常用的Qt位置相关函数和类&#xff1a; QPoint&#xff1a;QPoint类表示一个二维点的…...

vulnhub靶场 Kioptrix-level-1

简介&#xff1a; vulnhub是一个提供靶场环境的平台。而Kioptrix-level-1就是一个对新手比较友好的靶场。初学渗透的同学可以做做试试看&#xff0c;项目地址如下。 项目地址&#xff1a;Kioptrix: Level 1 (#1) ~ VulnHub 信息收集 查看本机IP&#xff0c;靶机跟kali都是使用…...

全网最细,真实企业性能测试落地实施,一文带你快速打通...

目录&#xff1a;导读 前言一、Python编程入门到精通二、接口自动化项目实战三、Web自动化项目实战四、App自动化项目实战五、一线大厂简历六、测试开发DevOps体系七、常用自动化测试工具八、JMeter性能测试九、总结&#xff08;尾部小惊喜&#xff09; 前言 1、什么是性能测试…...

三十一、【进阶】B+树的演变过程

1、B树简单介绍 &#xff08;1&#xff09;介绍&#xff1a;B树也属于B树&#xff0c;是B树的变种 &#xff08;2&#xff09;特点&#xff1a;所有的数据都位于叶子节点上&#xff0c;叶子节点上的所有元素形成了一个单项链表 &#xff08;3&#xff09;图示&#xff1a; 2…...

算法通过村第十三关-术数|白银笔记|术数高频问题

文章目录 前言数组实现加法专题数组实现整数加法字符串加法二进制加法 幂运算专题求2的次幂求3的次幂求4的次幂 总结 前言 提示&#xff1a;人心本易趋死寂&#xff0c;苦难之后&#xff0c;焕然重建&#xff0c;激荡一阵&#xff0c;又趋麻木。 --苏枕书《有鹿来》 我们继续看…...

Java 线程的生命周期

&#x1f648;作者简介&#xff1a;练习时长两年半的Java up主 &#x1f649;个人主页&#xff1a;程序员老茶 &#x1f64a; ps:点赞&#x1f44d;是免费的&#xff0c;却可以让写博客的作者开兴好久好久&#x1f60e; &#x1f4da;系列专栏&#xff1a;Java全栈&#xff0c;…...

Vue页面监听键盘按键的多种方法

在Vue页面中&#xff0c;可以使用多种方法来监听键盘按键。以下是至少五种常用的方法&#xff1a; 使用keydown或keyup指令来绑定键盘按键事件。 <template><div><input type"text" keydown.enter"handleEnterKey" /></div> <…...

解析硬件连通性测试的重要性及测试方法

在现代科技世界中&#xff0c;硬件设备的复杂性和多样性已经达到了前所未有的水平。无论是计算机、智能手机、物联网设备还是嵌入式系统&#xff0c;各种硬件组件的协同工作对于设备的正常运行至关重要。硬件连通性测试是确保这些组件相互配合无误的重要步骤。 一、硬件连通性测…...

Hive窗口函数回顾

1.语法 1.1 基于行的窗口函数 Hive的窗口函数分为两种类型&#xff0c;一种是基于行的窗口函数&#xff0c;即将某个字段的多行限定为一个范围&#xff0c;对范围内的字段值进行计算&#xff0c;最后将形成的字段拼接在该表上。 注意&#xff1a;在进行窗口函数计算之前&#…...

flink自定义窗口分配器

背景 我们知道处理常用的滑动窗口分配器&#xff0c;滚动窗口分配器&#xff0c;全局窗口分配器&#xff0c;会话窗口分配器外&#xff0c;我们可以实现自己的自定义窗口分配器&#xff0c;以实现我们的自己的窗口逻辑 自定义窗口分配器的实现 package wikiedits.assigner;i…...

iOS CGRect CGPoint NSRange等结构体的NSLog打印输出

iOS的UIKit里提供了UIGeometry.h内有各结构体转换成NSString的方法&#xff0c;可用于打印输出&#xff1b; UIKIT_EXTERN NSString *NSStringFromCGPoint(CGPoint point); UIKIT_EXTERN NSString *NSStringFromCGVector(CGVector vector); UIKIT_EXTERN NSString *NSStringFr…...

Viper FTP Mac/ftp管理工具

Viper FTP 是一个用于文件传输和管理的 Mac 应用程序。它允许用户上传、下载和管理远程服务器上的文件&#xff0c;以及在不同本地文件夹之间传输文件。 Viper FTP 支持广泛的文件传输协议&#xff0c;包括 FTP、SFTP、WebDav、Amazon S3、Google Drive 等。它还包括文件同步、…...

web漏洞-xml外部实体注入(XXE)

web漏洞-xml外部实体注入&#xff08;XXE&#xff09; 目录 web漏洞-xml外部实体注入&#xff08;XXE&#xff09;概念危害检测方法利用方法漏洞利用xxe-lab有回显情况无回显情况 pikachu靶场有回显内容无回显 修复方案 概念 xml可拓展标记语言&#xff1a; xml是一种可拓展的标…...

Impeller-Flutter的新渲染引擎

Impeller是什么&#xff1f;它本质上是怎样运行的&#xff1f; Impeller是Flutter的新的渲染引擎&#xff0c;直到现在Flutter正在用一个叫做Skia的渲染引擎。 问题是Skia不是为了Flutter量身定做的。它有为范围广阔的设备构建的一大堆的渲染特性&#xff0c;这意味着它并不总…...

python 面试算法题

1.第一题 题目描述:给定两个字符串, s 和 goal。如果在若干次旋转操作之后&#xff0c;s 能变成 goal &#xff0c;那么返回 true 。 s 的 旋转操作 就是将 s 最左边的字符移动到最右边。 例如, 若 s abcde&#xff0c;在旋转一次之后结果就是bcdea 。 示例一: 输入: s &quo…...

Python中的yield关键字

基本概念 yield 是 Python 中的一个关键字&#xff0c;主要在定义生成器函数时使用。使用 yield 的函数在调用时返回一个特殊的迭代器&#xff0c;称为生成器。不同于常规的函数返回一个单一的值&#xff08;如数字、字符串或其他对象&#xff09;&#xff0c;带有 yield 的函…...

怎么压缩pdf文件?分享缩小pdf文件的简单方法

在我们的日常生活和工作中&#xff0c;往往需要处理大量的PDF文件&#xff0c;而很多时候这些文件的大小会成为传输和存储的难题。为了解决这个问题&#xff0c;下面我们将介绍三种方法来压缩PDF文件&#xff0c;一起来看看吧~ 一、嗨格式压缩大师 首先&#xff0c;最简单也是…...

使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式

一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明&#xff1a;假设每台服务器已…...

微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】

微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来&#xff0c;Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...

DAY 47

三、通道注意力 3.1 通道注意力的定义 # 新增&#xff1a;通道注意力模块&#xff08;SE模块&#xff09; class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...

CentOS下的分布式内存计算Spark环境部署

一、Spark 核心架构与应用场景 1.1 分布式计算引擎的核心优势 Spark 是基于内存的分布式计算框架&#xff0c;相比 MapReduce 具有以下核心优势&#xff1a; 内存计算&#xff1a;数据可常驻内存&#xff0c;迭代计算性能提升 10-100 倍&#xff08;文档段落&#xff1a;3-79…...

Spring Boot面试题精选汇总

&#x1f91f;致敬读者 &#x1f7e9;感谢阅读&#x1f7e6;笑口常开&#x1f7ea;生日快乐⬛早点睡觉 &#x1f4d8;博主相关 &#x1f7e7;博主信息&#x1f7e8;博客首页&#x1f7eb;专栏推荐&#x1f7e5;活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...

[Java恶补day16] 238.除自身以外数组的乘积

给你一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O(n) 时间复杂度…...

selenium学习实战【Python爬虫】

selenium学习实战【Python爬虫】 文章目录 selenium学习实战【Python爬虫】一、声明二、学习目标三、安装依赖3.1 安装selenium库3.2 安装浏览器驱动3.2.1 查看Edge版本3.2.2 驱动安装 四、代码讲解4.1 配置浏览器4.2 加载更多4.3 寻找内容4.4 完整代码 五、报告文件爬取5.1 提…...

网站指纹识别

网站指纹识别 网站的最基本组成&#xff1a;服务器&#xff08;操作系统&#xff09;、中间件&#xff08;web容器&#xff09;、脚本语言、数据厍 为什么要了解这些&#xff1f;举个例子&#xff1a;发现了一个文件读取漏洞&#xff0c;我们需要读/etc/passwd&#xff0c;如…...

Web后端基础(基础知识)

BS架构&#xff1a;Browser/Server&#xff0c;浏览器/服务器架构模式。客户端只需要浏览器&#xff0c;应用程序的逻辑和数据都存储在服务端。 优点&#xff1a;维护方便缺点&#xff1a;体验一般 CS架构&#xff1a;Client/Server&#xff0c;客户端/服务器架构模式。需要单独…...

libfmt: 现代C++的格式化工具库介绍与酷炫功能

libfmt: 现代C的格式化工具库介绍与酷炫功能 libfmt 是一个开源的C格式化库&#xff0c;提供了高效、安全的文本格式化功能&#xff0c;是C20中引入的std::format的基础实现。它比传统的printf和iostream更安全、更灵活、性能更好。 基本介绍 主要特点 类型安全&#xff1a…...