广度优先(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)(例子:迷宫)
广度优先搜索算法(BFS)是一种用于图形和树数据结构的搜索算法。该算法从根节点开始搜索,然后依次访问每个相邻节点。在搜索过程中,每个节点都标记为已访问,以避免重复访问。BFS算法适用于寻找最短路径的问题࿰…...
【安卓源码】安卓Watchdog 机制
在Android系统中,也设计了一个软件层面Watchdog,用于保护一些重要的系统服务,比如:AMS、WMS、PMS等,由于以上核心服务运行在system_server进程里面,所以当以上服务出现异常时,通常会将system_se…...
inscode连接不上gpu,持续8小时,为了数据不丢失续费了6小时,我只想知道什么时候可以连接
并且给我相应的补偿...
QT位置相关函数
Qt(Qt Framework)是一个流行的C应用程序开发框架,提供了丰富的位置相关函数和类,用于处理窗口、窗口小部件和图形的位置和几何操作。以下是一些常用的Qt位置相关函数和类: QPoint:QPoint类表示一个二维点的…...
vulnhub靶场 Kioptrix-level-1
简介: vulnhub是一个提供靶场环境的平台。而Kioptrix-level-1就是一个对新手比较友好的靶场。初学渗透的同学可以做做试试看,项目地址如下。 项目地址:Kioptrix: Level 1 (#1) ~ VulnHub 信息收集 查看本机IP,靶机跟kali都是使用…...
全网最细,真实企业性能测试落地实施,一文带你快速打通...
目录:导读 前言一、Python编程入门到精通二、接口自动化项目实战三、Web自动化项目实战四、App自动化项目实战五、一线大厂简历六、测试开发DevOps体系七、常用自动化测试工具八、JMeter性能测试九、总结(尾部小惊喜) 前言 1、什么是性能测试…...
三十一、【进阶】B+树的演变过程
1、B树简单介绍 (1)介绍:B树也属于B树,是B树的变种 (2)特点:所有的数据都位于叶子节点上,叶子节点上的所有元素形成了一个单项链表 (3)图示: 2…...
算法通过村第十三关-术数|白银笔记|术数高频问题
文章目录 前言数组实现加法专题数组实现整数加法字符串加法二进制加法 幂运算专题求2的次幂求3的次幂求4的次幂 总结 前言 提示:人心本易趋死寂,苦难之后,焕然重建,激荡一阵,又趋麻木。 --苏枕书《有鹿来》 我们继续看…...
Java 线程的生命周期
🙈作者简介:练习时长两年半的Java up主 🙉个人主页:程序员老茶 🙊 ps:点赞👍是免费的,却可以让写博客的作者开兴好久好久😎 📚系列专栏:Java全栈,…...
Vue页面监听键盘按键的多种方法
在Vue页面中,可以使用多种方法来监听键盘按键。以下是至少五种常用的方法: 使用keydown或keyup指令来绑定键盘按键事件。 <template><div><input type"text" keydown.enter"handleEnterKey" /></div> <…...
解析硬件连通性测试的重要性及测试方法
在现代科技世界中,硬件设备的复杂性和多样性已经达到了前所未有的水平。无论是计算机、智能手机、物联网设备还是嵌入式系统,各种硬件组件的协同工作对于设备的正常运行至关重要。硬件连通性测试是确保这些组件相互配合无误的重要步骤。 一、硬件连通性测…...
Hive窗口函数回顾
1.语法 1.1 基于行的窗口函数 Hive的窗口函数分为两种类型,一种是基于行的窗口函数,即将某个字段的多行限定为一个范围,对范围内的字段值进行计算,最后将形成的字段拼接在该表上。 注意:在进行窗口函数计算之前&#…...
flink自定义窗口分配器
背景 我们知道处理常用的滑动窗口分配器,滚动窗口分配器,全局窗口分配器,会话窗口分配器外,我们可以实现自己的自定义窗口分配器,以实现我们的自己的窗口逻辑 自定义窗口分配器的实现 package wikiedits.assigner;i…...
iOS CGRect CGPoint NSRange等结构体的NSLog打印输出
iOS的UIKit里提供了UIGeometry.h内有各结构体转换成NSString的方法,可用于打印输出; UIKIT_EXTERN NSString *NSStringFromCGPoint(CGPoint point); UIKIT_EXTERN NSString *NSStringFromCGVector(CGVector vector); UIKIT_EXTERN NSString *NSStringFr…...
Viper FTP Mac/ftp管理工具
Viper FTP 是一个用于文件传输和管理的 Mac 应用程序。它允许用户上传、下载和管理远程服务器上的文件,以及在不同本地文件夹之间传输文件。 Viper FTP 支持广泛的文件传输协议,包括 FTP、SFTP、WebDav、Amazon S3、Google Drive 等。它还包括文件同步、…...
web漏洞-xml外部实体注入(XXE)
web漏洞-xml外部实体注入(XXE) 目录 web漏洞-xml外部实体注入(XXE)概念危害检测方法利用方法漏洞利用xxe-lab有回显情况无回显情况 pikachu靶场有回显内容无回显 修复方案 概念 xml可拓展标记语言: xml是一种可拓展的标…...
Impeller-Flutter的新渲染引擎
Impeller是什么?它本质上是怎样运行的? Impeller是Flutter的新的渲染引擎,直到现在Flutter正在用一个叫做Skia的渲染引擎。 问题是Skia不是为了Flutter量身定做的。它有为范围广阔的设备构建的一大堆的渲染特性,这意味着它并不总…...
python 面试算法题
1.第一题 题目描述:给定两个字符串, s 和 goal。如果在若干次旋转操作之后,s 能变成 goal ,那么返回 true 。 s 的 旋转操作 就是将 s 最左边的字符移动到最右边。 例如, 若 s abcde,在旋转一次之后结果就是bcdea 。 示例一: 输入: s &quo…...
Python中的yield关键字
基本概念 yield 是 Python 中的一个关键字,主要在定义生成器函数时使用。使用 yield 的函数在调用时返回一个特殊的迭代器,称为生成器。不同于常规的函数返回一个单一的值(如数字、字符串或其他对象),带有 yield 的函…...
怎么压缩pdf文件?分享缩小pdf文件的简单方法
在我们的日常生活和工作中,往往需要处理大量的PDF文件,而很多时候这些文件的大小会成为传输和存储的难题。为了解决这个问题,下面我们将介绍三种方法来压缩PDF文件,一起来看看吧~ 一、嗨格式压缩大师 首先,最简单也是…...
在rocky linux 9.5上在线安装 docker
前面是指南,后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...
JVM垃圾回收机制全解析
Java虚拟机(JVM)中的垃圾收集器(Garbage Collector,简称GC)是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象,从而释放内存空间,避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...
ffmpeg(四):滤镜命令
FFmpeg 的滤镜命令是用于音视频处理中的强大工具,可以完成剪裁、缩放、加水印、调色、合成、旋转、模糊、叠加字幕等复杂的操作。其核心语法格式一般如下: ffmpeg -i input.mp4 -vf "滤镜参数" output.mp4或者带音频滤镜: ffmpeg…...
实现弹窗随键盘上移居中
实现弹窗随键盘上移的核心思路 在Android中,可以通过监听键盘的显示和隐藏事件,动态调整弹窗的位置。关键点在于获取键盘高度,并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...
MySQL用户和授权
开放MySQL白名单 可以通过iptables-save命令确认对应客户端ip是否可以访问MySQL服务: test: # iptables-save | grep 3306 -A mp_srv_whitelist -s 172.16.14.102/32 -p tcp -m tcp --dport 3306 -j ACCEPT -A mp_srv_whitelist -s 172.16.4.16/32 -p tcp -m tcp -…...
Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)
参考官方文档:https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java(供 Kotlin 使用) 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...
3-11单元格区域边界定位(End属性)学习笔记
返回一个Range 对象,只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意:它移动的位置必须是相连的有内容的单元格…...
MySQL账号权限管理指南:安全创建账户与精细授权技巧
在MySQL数据库管理中,合理创建用户账号并分配精确权限是保障数据安全的核心环节。直接使用root账号进行所有操作不仅危险且难以审计操作行为。今天我们来全面解析MySQL账号创建与权限分配的专业方法。 一、为何需要创建独立账号? 最小权限原则…...
Go 语言并发编程基础:无缓冲与有缓冲通道
在上一章节中,我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道,它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好࿰…...
【从零学习JVM|第三篇】类的生命周期(高频面试题)
前言: 在Java编程中,类的生命周期是指类从被加载到内存中开始,到被卸载出内存为止的整个过程。了解类的生命周期对于理解Java程序的运行机制以及性能优化非常重要。本文会深入探寻类的生命周期,让读者对此有深刻印象。 目录 …...
