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

【洛谷刷题】蓝桥杯专题突破-广度优先搜索-bfs(13)

目录

写在前面:

题目:P1443 马的遍历 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

        题目描述:

        输入格式:

        输出格式:

        输入样例:

        输出样例:

解题思路:

代码:

AC !!!!!!!!!!

写在最后:


写在前面:

怎么样才能学好一个算法?

我个人认为,系统性的刷题尤为重要,

所以,为了学好广度优先搜索,为了用好搜索应对蓝桥杯,

事不宜迟,我们即刻开始刷题!

题目:P1443 马的遍历 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目描述:

输入格式:

输入只有一行四个整数,分别为n, m, x, y。

输出格式:

一个 n × m 的矩阵,代表马到达某个点最少要走几步(不能到达则输出 −1)。

输入样例:

3 3 1 1

输出样例:


输出 #1复制
0    3    2    
3    -1   1    
2    1    4   

解题思路:

我们根据这道题的数据范围,可以判断出,

这道题需要使用广度优先搜索,题目要求是,

找出马到一个点最少需要几步,

我们用bfs,一层层搜索他的情况即可,

那么我们先来模拟一下题目给出的用例:

这个是我们的起点:

 在象棋中,马走日字,在这个矩阵中,

它有两个位置可以走:

所以那两个位置被置为1,

表明马已经走了一步,

我们让马继续走:

马有走到这些位置,

继续记录路径和:

 马继续走,以此类推,最后就会走到目标点位:

 

 我们根据上面的规律实现代码,

但是这一次,我打算换一种方式,

因为调用STL库中的队列速度是比较慢的,

我们可以自己用数组模拟一个队列,

这样可以加快效率,

我们应该怎么实现呢?

我们可以用头尾两个指针维护这个队列,

往队列插入一个数:

 如果要出队,那就让队头++,

这样就访问不了那个数了:

如果要入队,

就让队尾 tail++,再q[tail] = x。

如果队头大于队尾,那就证明队列为空:

  

下面是代码实现:

代码:

//包好头文件
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;int n, m, x, y;const int N = 500;//存坐标
typedef pair<int, int> PII;//存马的步数
int dist[N][N];//用数组模拟队列
PII q[N * N];//存坐标偏移量
int dx[] = {2, 2, 1, 1, -1, -1, -2, -2};
int dy[] = {1, -1, 2, -2, 2, -2, 1, -1};void bfs(int x, int y)
{//初始化memset(dist, -1, sizeof(dist));//插入第一个数据q[0] = {x, y};dist[x][y] = 0;int head = 0;int tail = 0;//如果头指针大于尾指针,证明队列为空while(head <= tail){auto t = q[head];head++;for(int i = 0; i < 8; i++){int a = dx[i] + t.first;int b = dy[i] + t.second;//控边界if(a < 1 || a > n || b < 1 || b > m) continue;if(dist[a][b] >= 0) continue;//记录马的步数dist[a][b] = dist[t.first][t.second] + 1;//入队tail++;q[tail] = {a, b};   }}
}int main()
{scanf("%d %d %d %d", &n, &m, &x, &y);bfs(x, y);for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){printf("%-5d", dist[i][j]);}printf("\n");}return 0;
}

AC !!!!!!!!!!

写在最后:

以上就是本篇文章的内容了,感谢你的阅读。

如果喜欢本文的话,欢迎点赞和评论,写下你的见解。

如果想和我一起学习编程,不妨点个关注,我们一起学习,一同成长。

之后我还会输出更多高质量内容,欢迎收看。 

相关文章:

【洛谷刷题】蓝桥杯专题突破-广度优先搜索-bfs(13)

目录 写在前面&#xff1a; 题目&#xff1a;P1443 马的遍历 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 题目描述&#xff1a; 输入格式&#xff1a; 输出格式&#xff1a; 输入样例&#xff1a; 输出样例&#xff1a; 解题思路&#xff1a; 代码&#xff1a; AC &am…...

【新2023Q2模拟题JAVA】华为OD机试 - 总最快检测效率 or 核酸检测效率

最近更新的博客 华为od 2023 | 什么是华为od,od 薪资待遇,od机试题清单华为OD机试真题大全,用 Python 解华为机试题 | 机试宝典【华为OD机试】全流程解析+经验分享,题型分享,防作弊指南华为od机试,独家整理 已参加机试人员的实战技巧本篇题解:报数 题目 一百个人围成一圈…...

基于主成分分析的混音方法

一、简介&#xff1a; 基于主成分分析的混音方法是一种常见的音频混音技术&#xff0c;它利用主成分分析&#xff08;PCA&#xff09;对音频信号进行降维和重构&#xff0c;从而实现混音。 二、基本步骤如下&#xff1a; 采集和存储需要混音的音频信号。 对音频信号进行主成分…...

Code Two Exchange Crack

CodeTwo Exchange 迁移允许直接从早期版本的 Exchange&#xff08;从 Exchange 2010 开始&#xff09;安全、轻松地迁移到 Exchange 2019 和 2016。此服务器应用程序还允许您集中管理来自 Microsoft 365 (Office 365) 的邮箱迁移以及来自基于 IMAP 的电子邮件系统&#xff08;例…...

jQuery.form.js 详细用法_维护老项目使用

概述 jquery-3.3.1.min.js &#xff1a; http://jquery.com/download jquery.form.min.js &#xff1a;http://malsup.com/jquery/form/#tab7 jquery form 是一个表单异步提交的插件&#xff0c;可以很容易提交表单&#xff0c;设置表单提交的参数&#xff0c;并在表单提交前…...

【Java】关于你不知道的Java大整数运算之BigInteger类超级好用!!!

目录 一、BigInteger类简单介绍 二、BigInteger构造方式 &#xff08;1&#xff09;构造方式 &#xff08;2&#xff09;输入方式 三、BigInteger常见的成员方法 &#xff08;1&#xff09;方法介绍 &#xff08;2&#xff09;方法使用演示 1.加减乘除余 2.比较 3.绝…...

运维是不是没有出路了?

瑞典马工的​​《是时候让运维集体下岗了》一出&#xff0c;就让运维人为之一颤&#xff0c;​人人自危。文章开篇就提到&#xff1a;​​明人不说暗话&#xff0c;在云原生和DevOps成熟的今天&#xff0c;运维作为一个岗位和团队已经完成了历史任务&#xff0c;应该退出舞台了…...

【C++笔试强训】第七天

选择题 解析&#xff1a;内联函数&#xff08;inline&#xff09;一般用于代码较少&#xff0c;代码块里面没有递归且频繁调用的函数&#xff0c;是一种以空间换时间&#xff08;不是指内存&#xff0c;而是指令变多编译出来的可执行程序会变大&#xff09;的做法。内联函数在预…...

mysql binlog 一直追加写,磁盘满了怎么办?

文章目录 mysql binlog 清理策略1、设置binlog最大的文件数和文件大小2、定时清理过期binlog文件3、手动清理binlog文件4、禁用或启用binlogmysql binlog用于记录mysql数据库所有变更(数据库的DDL、DML操作)包括用户执行的语句,以及底层引擎所执行的操作的二进制日志,主要用…...

缓存穿透、缓存雪崩、缓存击穿解决方案

什么是缓存 缓存就是数据交换的缓冲区&#xff08;称作Cache&#xff09;,是存贮数据的临时地方&#xff0c;一般读写性能较高。 添加 redis 缓存 给店铺类型查询业务添加缓存 需求&#xff1a;添加ShopTypeController中的queryTypeList方法&#xff0c;添加查询缓存 缓存更新…...

web + servlet + jdbc mysql 实现简单的表单管理界面

目录数据库创建数据库连接servlet创建,这里注意一下我的数据库我自己改了一下名字lhx网页html运行文件目录展示首先我们准备好开发使用的工具以及配置 idea2020 tomcat8.5 创建javaweb参考idea编译Tomcat详细步骤 IDEA通过JDBC连接数据库请参考jdbc连接数据库 需要登陆注册界面…...

Maven 国内镜像仓库

镜像仓库目标 当我们未定义任何远程仓库时&#xff0c;使用 Maven 更新依赖时&#xff0c;其会去默认远程仓库中拉取&#xff0c;默认远程仓库 是国外地址&#xff0c;所以在国内访问特别慢&#xff0c;想提升访问速度&#xff0c;需要将国外地址换成国内地址 更换仓库地址的…...

day21 ● 530.二叉搜索树的最小绝对差 ● 501.二叉搜索树中的众数 ● 236. 二叉树的最近公共祖先

二叉搜索树的最小绝对差 二叉搜索树&#xff08;Binary Search Tree&#xff0c;简称 BST&#xff09;是一种特殊的二叉树&#xff0c;它的每个节点都满足以下条件&#xff1a; 左子树上所有节点的值均小于该节点的值&#xff1b;右子树上所有节点的值均大于该节点的值&#…...

大学计算机(软件类)专业推荐竞赛 / 证书 官网及赛事相关信息整理

大学计算机专业(软件)推荐竞赛 / 证书 官网及赛事相关信息 一、算法类(丰富简历)&#xff1a; 1、ACM国际大学生程序设计竞赛&#xff1a; 官网&#xff1a;https://icpc.global/ 国内&#xff1a;http://icpc.pku.edu.cn/index.htm 报名方式&#xff1a;区域预赛一般每年9-1…...

Metasploit入门到高级【第九章】

预计更新第一章&#xff1a;Metasploit 简介 Metasploit 是什么Metasploit 的历史和发展Metasploit 的组成部分 第二章&#xff1a;Kali Linux 入门 Kali Linux 简介Kali Linux 安装和配置常用命令和工具介绍 第三章&#xff1a;Metasploit 基础 Metasploit 的基本概念Met…...

JDK之8后: 协程? 虚拟线程!!!

特性官方文档: https://openjdk.org/jeps/436 Java协程 近三十年来&#xff0c;Java 开发人员一直依赖线程作为并发服务器应用程序的构建块。每个方法中的每个语句都在线程内执行&#xff0c;并且由于 Java 是多线程的&#xff0c;因此多个执行线程同时发生。线程是Java的并发…...

体验 jeecg

体验 jeecg官网地址事前准备安装升级 node 和 npm 版本验证安装安装 pnpm clidocker 启动 MySQLdocker 启动 redisgit clone 项目启动JAVA项目 jeecg-boot启动Vue3项目 jeecgboot-vue3官网地址 http://www.jeecg.com/ 事前准备 (1) 为了回避Could not find artifact com.mic…...

投稿指南【NO.13】计算机学会CCF推荐期刊和会议分享(人工智能)

前 言国内高等院校研究生及博士毕业条件需要发表高水平期刊或者顶会&#xff08;清北上交等重点学校毕业要求为至少发一篇顶会&#xff09;&#xff0c;很多同学私信问到一级学会的会议论文怎么找、是什么&#xff0c;比如前段时间放榜的CVPR论文就是人工智能领域的顶会国际会议…...

一份sql笔试

1、 select substr(time,1,10),count(order_id),count(distinct passenger_id) from order where substr(time,1,7)2023-08 group by substr(time,1,10) order by substr(time,1,10);2、 select city_id from (select * from order where substr(time,1,7) 2022-08) t1 left j…...

交换瓶子

交换瓶子 贡献者&#xff1a;programmer_ada 有N个瓶子&#xff0c;编号 1 ~ N&#xff0c;放在架子上。 比如有5个瓶子&#xff1a; 2 1 3 5 4 要求每次拿起2个瓶子&#xff0c;交换它们的位置。 经过若干次后&#xff0c;使得瓶子的序号为&#xff1a; 1 2 3 4 5 对于这么…...

卷积神经网络原理与Baichuan-M2-32B医疗图像识别实战

卷积神经网络原理与Baichuan-M2-32B医疗图像识别实战 1. 引言 医疗图像识别一直是人工智能领域的重要应用方向。传统的图像识别方法往往需要大量的人工特征工程&#xff0c;而卷积神经网络的出现彻底改变了这一局面。今天&#xff0c;我们将深入探讨卷积神经网络的核心原理&a…...

N_m3u8DL-RE流媒体下载器:多协议解析技术突破与下载效率提升

N_m3u8DL-RE流媒体下载器&#xff1a;多协议解析技术突破与下载效率提升 【免费下载链接】N_m3u8DL-RE 跨平台、现代且功能强大的流媒体下载器&#xff0c;支持MPD/M3U8/ISM格式。支持英语、简体中文和繁体中文。 项目地址: https://gitcode.com/GitHub_Trending/nm3/N_m3u8D…...

不会写C代码也能做飞控?手把手教你用Matlab/Simulink和FMT搭建无人机算法模型

零代码飞控开发实战&#xff1a;用Matlab/SimulinkFMT实现无人机算法快速迭代 当无人机行业从极客玩具转向工业级应用时&#xff0c;传统飞控开发模式正面临严峻挑战——某高校研究团队曾花费三个月手工编写PID控制代码&#xff0c;却在首次试飞时因姿态解算模块的数值溢出导致…...

告别广告侵扰:AdGuard广告拦截扩展全平台部署指南

告别广告侵扰&#xff1a;AdGuard广告拦截扩展全平台部署指南 【免费下载链接】AdguardBrowserExtension AdGuard browser extension 项目地址: https://gitcode.com/gh_mirrors/ad/AdguardBrowserExtension 副标题&#xff1a;从新手到高手的一站式配置方案 一、价值定…...

bert-base-chinese详细步骤:如何将test.py改造成支持流式文本处理的微服务

bert-base-chinese详细步骤&#xff1a;如何将test.py改造成支持流式文本处理的微服务 1. 项目背景与价值 在实际的工业场景中&#xff0c;我们经常需要处理大量的文本数据流。传统的批处理方式虽然简单&#xff0c;但无法满足实时性要求高的应用场景。比如智能客服系统需要实…...

Inner-IoU: More Effective Intersection over Union Loss with Auxiliary Bounding Box——基于辅助边界框的更有效交并比损失

这篇题为《Inner-IoU: More Effective Intersection over Union Loss with Auxiliary Bounding Box》的论文&#xff0c;主要研究了目标检测中边界框回归&#xff08;BBR&#xff09;损失函数的改进问题。以下是其核心研究内容的全面总结概括&#xff1a; 1. 研究背景与问题 现…...

DriverStore Explorer完全指南:免费Windows驱动管理终极教程

DriverStore Explorer完全指南&#xff1a;免费Windows驱动管理终极教程 【免费下载链接】DriverStoreExplorer Driver Store Explorer [RAPR] 项目地址: https://gitcode.com/gh_mirrors/dr/DriverStoreExplorer DriverStore Explorer是一款功能强大的Windows驱动程序管…...

ESP32 FreeRTOS任务状态全解析:从就绪态到挂起态的深度理解与应用

ESP32 FreeRTOS任务状态全解析&#xff1a;从就绪态到挂起态的深度理解与应用 在嵌入式系统开发中&#xff0c;任务调度是实时操作系统(RTOS)的核心功能之一。对于ESP32开发者而言&#xff0c;深入理解FreeRTOS的任务状态模型&#xff0c;能够帮助我们编写出更高效、更可靠的多…...

墨语灵犀镜像灰度发布:Kubernetes滚动更新无感升级实践

墨语灵犀镜像灰度发布&#xff1a;Kubernetes滚动更新无感升级实践 1. 引言&#xff1a;优雅升级的艺术挑战 在现代应用部署中&#xff0c;如何实现平滑无感的服务升级一直是个技术难题。特别是对于「墨语灵犀」这样注重用户体验的深度翻译工具&#xff0c;任何服务中断或体验…...

从零开始:用STM32CubeMX+Keil5开发计算器的5个关键陷阱与解决方案

从零开始&#xff1a;用STM32CubeMXKeil5开发计算器的5个关键陷阱与解决方案 当你第一次尝试用STM32CubeMX和Keil5开发一个计算器时&#xff0c;可能会觉得这不过是几个简单数学运算的组合。但真正动手后&#xff0c;你会发现从工具链配置到算法实现&#xff0c;处处都是"…...