【洛谷刷题】蓝桥杯专题突破-广度优先搜索-bfs(12)
目录
写在前面:
题目:P1746 离开中山路 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题目描述:
输入格式:
输出格式:
输入样例:
输出样例:
解题思路:
代码:
AC !!!!!!!!!!
写在最后:
写在前面:
怎么样才能学好一个算法?
我个人认为,系统性的刷题尤为重要,
所以,为了学好广度优先搜索,为了用好搜索应对蓝桥杯,
事不宜迟,我们即刻开始刷题!
题目:P1746 离开中山路 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题目描述:

输入格式:
第 1 行包含一个数 n。
第 2 行到第 n + 1 行:整个地图描述
(00 表示马路,11 表示店铺,注意两个数之间没有空格)。
第 n + 2 行:四个数 x1, y1, x2, y2。
输出格式:
只有 11 行,即最短到达目的地距离。
输入样例:
3
001
101
100
1 1 3 3
输出样例:
4
解题思路:
这道题也是一道基础的迷宫问题,
我们用搜索来做,然后观察一下他的数据范围,
地图1000乘1000的大小,
很明显dfs会超时,所以这道题需要使用bfs进行搜索,
我们先来看一下地图的样例,模拟一下:
我们从坐标1,1开始:

然后直接往四个方向搜索即可:

一直搜索到目标终点:

所以最后返回的最短路径就是4,
那么其实我们可以发现,题目中有个求最短路径的这个字眼,
我们可以判断这道题多半是个bfs的题目。
根据这个思路,我们开始实现代码:
代码:
//包好头文件
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;const int N = 1010;//存坐标
typedef pair<int, int> PII;int n;
int x1, y1, x2, y2;//记录路径和
int dist[N][N];//存地图
char g[N][N];queue<PII> q;//存偏移量
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};int bfs(int x1, int y1)
{//将dist初始化为-1memset(dist, -1, sizeof(dist));q.push({x1, y1});//起点dist[x1][y1] = 0;//遍历到找到终点值或者队列为空while(!q.empty()){//取队头auto t = q.front();q.pop();for(int i = 0; i < 4; i++){int a = t.first + dx[i];int b = t.second + dy[i];//控边界if(a < 1 || a > n || b < 1 || b > n) continue;if(dist[a][b] >= 0) continue;if(g[a][b] != '0') continue;q.push({a, b});//记录路径和dist[a][b] = dist[t.first][t.second] + 1;//如果到终点了,就直接返回终点值if(dist[x2][y2] > 0)return dist[x2][y2];}}//如果走不到终点,返回-1return -1;
}int main()
{scanf("%d", &n);for(int i = 1; i <= n; i++){scanf("%s", g[i] + 1);}scanf("%d %d %d %d", &x1, &y1, &x2, &y2);int res = bfs(x1, y1);printf("%d", res);return 0;
}
AC !!!!!!!!!!

写在最后:
以上就是本篇文章的内容了,感谢你的阅读。
如果喜欢本文的话,欢迎点赞和评论,写下你的见解。
如果想和我一起学习编程,不妨点个关注,我们一起学习,一同成长。
之后我还会输出更多高质量内容,欢迎收看。
相关文章:
【洛谷刷题】蓝桥杯专题突破-广度优先搜索-bfs(12)
目录 写在前面: 题目:P1746 离开中山路 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 题目描述: 输入格式: 输出格式: 输入样例: 输出样例: 解题思路: 代码: …...
【数据结构】堆(堆的实现 堆向下调整算法 堆的创建 堆的插入 堆的删除 堆的代码实现 堆的应用)
文章目录堆的实现堆向下调整算法堆的创建堆的插入堆的删除堆的代码实现堆的应用堆的实现 堆是属于操作系统进程地址空间内存区域的划分。 我们下面实现数据结构中的堆。 堆是一个完全二叉树:分为小根堆和大根堆。 小根堆:任何一个节点的值都<孩子的…...
JDBC数据库驱动的下载与安装与连接
目录 JDBC数据库驱动下载 Intellij IDEA安装JDBC驱动 在使用 JDBC 之前,需要下载相应的 JDBC 驱动程序,该驱动程序应该与你使用的数据库的版本相对应。可以在数据库官网上找到相应的 JDBC 驱动程序。 JDBC数据库驱动下载 点击官方链接 MySQL :: MySQ…...
如何更改 PDF 背景颜色?
PDF 是用于简洁演示的文件格式,许多员工都参考它来演示文件。如果您想要 PDF 文本的最佳对比度方案,我们建议您更改PDF 背景颜色。您甚至可以更改 PDF 颜色的文本,但它不会有太大吸引力,而是尝试使用 PDF 背景更改器应用程序。如果…...
room数据库使用以及增加表的使用
依赖 "androidx.room:room-runtime:2.2.6" "androidx.room:room-compiler:2.2.6" 1.实体类 实体类需要保存到数据库的新类用Entity注解表示 tableName是数据库中表的名字,my_advert可以根据自己需要自定义 PrimaryKey,NonNull主键…...
WiFi-交互过程分析
目录 1.802.11 标准简介 2.802.11 协议格式 2.1管理帧协议格式 2.1.1(Beacon (信标) 帧) 2.1.2(Probe Request (探测请求) 帧) 2.1.3(Probe Response (探测响应) 帧) 2.1.4(ATIM 帧) 2.1.5(Disassociation (解除关联) 与 Deauthentication (解除认证) 帧) 2.1.6(Assoc…...
基于ZYNQ+linux+xenomai 的多轴运动控制平台关键技术研发-测试系统搭建(四)
本章搭建实验测试平台,对多轴运动控制平台的硬件功能和系统任务通信功能 进行测试。通过测试结果,进行平台硬件设计正确性验证和系统实时处理与同步控制 的功能与性能验证。 5.1 测试平台搭建 多轴运动控制系统的测试平台搭建如图 5.1 所示。测试平台由安…...
初识操作系统
目录 1.操作系统是什么 2.为什么要有操作系统 3.操作系统的相关关系 1.驱动程序 2.系统调用接口 3.用户调用接口 4.用户程序 4.用具体的例子理解操作系统 1.操作系统是什么 (1)操作系统是一组管理计算机硬件与软件资源的计算机软件程序 。 (…...
#详细介绍!!!线程池
本篇详细: 1.介绍了什么是线程池 2.使用线程池有什么好处 3.线程池的工作流程 4.线程池的各个参数介绍 5.如何编写Java代码来创建线程池 6.使用线程池的注意事项 目录 一:什么是线程池 二:为什么使用线程池来管理线程 三:线程池…...
【嵌入式Linux学习笔记】基于Linux官方库的标准外设驱动
对于标准的外设如LED,KEY,PWM等,以及标准通信协议,Linux都自带有标准的驱动库,不需要我们自行编写,只需要配置好相应的GPIO属性和电气属性,即可匹配相应的驱动,在应用程序中直接使用…...
网络爬虫抓包工具
📚介绍:Charles是著名的抓包工具🐂,可以抓取移动端与pc端网络访问🕷的所有数据。我们将使用它抓取我们与小程序交互的所有信息。🎇我们可以百度搜索Charles官网下载适用于自己系统的Charles安装包…...
蓝桥杯倒计时 | 倒计时17天
作者🕵️♂️:让机器理解语言か 专栏🎇:蓝桥杯倒计时冲刺 描述🎨:蓝桥杯冲刺阶段,一定要沉住气,一步一个脚印,胜利就在前方! 寄语💓:…...
【Spring Cloud Alibaba】7.Sentinel熔断器仪表盘监控
文章目录简介什么是 Sentinel控制台获取源码方式下载jar包方式启动访问服务配置项目,启用Sentinel完整配置测试简介 接下来我们通过Sentinel控制台来实现对服务消费者提供的熔断机制进行监控和控制,本操作先要完成之前的步骤,详情请参照【Sp…...
个人博客系统项目测试报告
项目背景介绍 背景:当在学习一项技能的时候,我们总会习惯通过博客来记录所学的知识点,方便后期遗忘时随时查看和快速复习。本次开发的Web网站程序便是为了更加轻量和方便地记录自己的学习笔记 概述:一个Web网站程序,…...
flutter安装自用笔记
参照文章: 开发环境搭建 Flutter环境配置步骤: 1.系统配置要求 2.Java环境 3.Flutter SDK 4.Android 开发环境一、系统配置要求 操作系统:Windows 7 SP1 或更高的版本(基于 x86-64 的 64 位操作系统) 磁盘空间&…...
tomcat线程池以及在SpringBoot中的启动过程
tomcat两大组件:连接器Connector,容器Container tomcat线程池 Tomcat线程池扩展了ThreadPoolExecutor,行为稍有不同 重写了ThreadPoolExecutor的execute方法 如果总线程数达到maximumPoolSize,不会立刻抛RejectedExecutionExcept…...
第十四届中国大学生创新创业大赛
文章目录比赛官网比赛题目含金量非常高建议参加的学生推荐几个我感兴趣的题目联系比赛官网 官网地址:http://www.fwwb.org.cn/ 实际叫做:中国大学生创新创业大赛 比赛题目 题目公布查看地址:http://www.fwwb.org.cn/topic/index 题目有…...
LeetCode:322. 零钱兑换——动态规划从案例入门
🍎道阻且长,行则将至。🍓 🌻算法,不如说它是一种思考方式🍀算法专栏: 👉🏻123 一、🌱322. 零钱兑换 题目描述:给你一个整数数组coins,…...
【lwIP(第四章)】网络接口
目录一、lwIP网络接口简介二、lwIP的netif结构三、lwIP的netif相关函数1. lwIP网络接口的全局变量2. netif_add()函数3. netif_remove()函数4. netif_set_default()函数一、lwIP网络接口简介 lwIP协议栈支持多种不同的网络接口(网卡),由于网卡…...
Vue3 pinia入门篇(一)
系列文章目录 主要为了记录如何使用Pinia在Vue3中的使用方式(下面会介绍为什么使用Vue3选型) 文章目录系列文章目录不用Vue2使用Pinia举例子?1.笔者的个人看法:2.总结一、Pinia是什么1.状态管理工具(类比Vuexÿ…...
FFmpeg 低延迟同屏方案
引言 在实时互动需求激增的当下,无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作,还是游戏直播的画面实时传输,低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架,凭借其灵活的编解码、数据…...
从深圳崛起的“机器之眼”:赴港乐动机器人的万亿赛道赶考路
进入2025年以来,尽管围绕人形机器人、具身智能等机器人赛道的质疑声不断,但全球市场热度依然高涨,入局者持续增加。 以国内市场为例,天眼查专业版数据显示,截至5月底,我国现存在业、存续状态的机器人相关企…...
Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器
第一章 引言:语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域,文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量,支撑着搜索引擎、推荐系统、…...
Spring Boot面试题精选汇总
🤟致敬读者 🟩感谢阅读🟦笑口常开🟪生日快乐⬛早点睡觉 📘博主相关 🟧博主信息🟨博客首页🟫专栏推荐🟥活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...
Springboot社区养老保险系统小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,社区养老保险系统小程序被用户普遍使用,为方…...
基于 TAPD 进行项目管理
起因 自己写了个小工具,仓库用的Github。之前在用markdown进行需求管理,现在随着功能的增加,感觉有点难以管理了,所以用TAPD这个工具进行需求、Bug管理。 操作流程 注册 TAPD,需要提供一个企业名新建一个项目&#…...
在鸿蒙HarmonyOS 5中使用DevEco Studio实现企业微信功能
1. 开发环境准备 安装DevEco Studio 3.1: 从华为开发者官网下载最新版DevEco Studio安装HarmonyOS 5.0 SDK 项目配置: // module.json5 {"module": {"requestPermissions": [{"name": "ohos.permis…...
WebRTC从入门到实践 - 零基础教程
WebRTC从入门到实践 - 零基础教程 目录 WebRTC简介 基础概念 工作原理 开发环境搭建 基础实践 三个实战案例 常见问题解答 1. WebRTC简介 1.1 什么是WebRTC? WebRTC(Web Real-Time Communication)是一个支持网页浏览器进行实时语音…...
【p2p、分布式,区块链笔记 MESH】Bluetooth蓝牙通信 BLE Mesh协议的拓扑结构 定向转发机制
目录 节点的功能承载层(GATT/Adv)局限性: 拓扑关系定向转发机制定向转发意义 CG 节点的功能 节点的功能由节点支持的特性和功能决定。所有节点都能够发送和接收网格消息。节点还可以选择支持一个或多个附加功能,如 Configuration …...
快速排序算法改进:随机快排-荷兰国旗划分详解
随机快速排序-荷兰国旗划分算法详解 一、基础知识回顾1.1 快速排序简介1.2 荷兰国旗问题 二、随机快排 - 荷兰国旗划分原理2.1 随机化枢轴选择2.2 荷兰国旗划分过程2.3 结合随机快排与荷兰国旗划分 三、代码实现3.1 Python实现3.2 Java实现3.3 C实现 四、性能分析4.1 时间复杂度…...
