【洛谷刷题】蓝桥杯专题突破-广度优先搜索-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)
目录 写在前面: 题目:P1443 马的遍历 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 题目描述: 输入格式: 输出格式: 输入样例: 输出样例: 解题思路: 代码: AC &am…...
【新2023Q2模拟题JAVA】华为OD机试 - 总最快检测效率 or 核酸检测效率
最近更新的博客 华为od 2023 | 什么是华为od,od 薪资待遇,od机试题清单华为OD机试真题大全,用 Python 解华为机试题 | 机试宝典【华为OD机试】全流程解析+经验分享,题型分享,防作弊指南华为od机试,独家整理 已参加机试人员的实战技巧本篇题解:报数 题目 一百个人围成一圈…...
基于主成分分析的混音方法
一、简介: 基于主成分分析的混音方法是一种常见的音频混音技术,它利用主成分分析(PCA)对音频信号进行降维和重构,从而实现混音。 二、基本步骤如下: 采集和存储需要混音的音频信号。 对音频信号进行主成分…...
Code Two Exchange Crack
CodeTwo Exchange 迁移允许直接从早期版本的 Exchange(从 Exchange 2010 开始)安全、轻松地迁移到 Exchange 2019 和 2016。此服务器应用程序还允许您集中管理来自 Microsoft 365 (Office 365) 的邮箱迁移以及来自基于 IMAP 的电子邮件系统(例…...
jQuery.form.js 详细用法_维护老项目使用
概述 jquery-3.3.1.min.js : http://jquery.com/download jquery.form.min.js :http://malsup.com/jquery/form/#tab7 jquery form 是一个表单异步提交的插件,可以很容易提交表单,设置表单提交的参数,并在表单提交前…...
【Java】关于你不知道的Java大整数运算之BigInteger类超级好用!!!
目录 一、BigInteger类简单介绍 二、BigInteger构造方式 (1)构造方式 (2)输入方式 三、BigInteger常见的成员方法 (1)方法介绍 (2)方法使用演示 1.加减乘除余 2.比较 3.绝…...
运维是不是没有出路了?
瑞典马工的《是时候让运维集体下岗了》一出,就让运维人为之一颤,人人自危。文章开篇就提到:明人不说暗话,在云原生和DevOps成熟的今天,运维作为一个岗位和团队已经完成了历史任务,应该退出舞台了…...
【C++笔试强训】第七天
选择题 解析:内联函数(inline)一般用于代码较少,代码块里面没有递归且频繁调用的函数,是一种以空间换时间(不是指内存,而是指令变多编译出来的可执行程序会变大)的做法。内联函数在预…...
mysql binlog 一直追加写,磁盘满了怎么办?
文章目录 mysql binlog 清理策略1、设置binlog最大的文件数和文件大小2、定时清理过期binlog文件3、手动清理binlog文件4、禁用或启用binlogmysql binlog用于记录mysql数据库所有变更(数据库的DDL、DML操作)包括用户执行的语句,以及底层引擎所执行的操作的二进制日志,主要用…...
缓存穿透、缓存雪崩、缓存击穿解决方案
什么是缓存 缓存就是数据交换的缓冲区(称作Cache),是存贮数据的临时地方,一般读写性能较高。 添加 redis 缓存 给店铺类型查询业务添加缓存 需求:添加ShopTypeController中的queryTypeList方法,添加查询缓存 缓存更新…...
web + servlet + jdbc mysql 实现简单的表单管理界面
目录数据库创建数据库连接servlet创建,这里注意一下我的数据库我自己改了一下名字lhx网页html运行文件目录展示首先我们准备好开发使用的工具以及配置 idea2020 tomcat8.5 创建javaweb参考idea编译Tomcat详细步骤 IDEA通过JDBC连接数据库请参考jdbc连接数据库 需要登陆注册界面…...
Maven 国内镜像仓库
镜像仓库目标 当我们未定义任何远程仓库时,使用 Maven 更新依赖时,其会去默认远程仓库中拉取,默认远程仓库 是国外地址,所以在国内访问特别慢,想提升访问速度,需要将国外地址换成国内地址 更换仓库地址的…...
day21 ● 530.二叉搜索树的最小绝对差 ● 501.二叉搜索树中的众数 ● 236. 二叉树的最近公共祖先
二叉搜索树的最小绝对差 二叉搜索树(Binary Search Tree,简称 BST)是一种特殊的二叉树,它的每个节点都满足以下条件: 左子树上所有节点的值均小于该节点的值;右子树上所有节点的值均大于该节点的值&#…...
大学计算机(软件类)专业推荐竞赛 / 证书 官网及赛事相关信息整理
大学计算机专业(软件)推荐竞赛 / 证书 官网及赛事相关信息 一、算法类(丰富简历): 1、ACM国际大学生程序设计竞赛: 官网:https://icpc.global/ 国内:http://icpc.pku.edu.cn/index.htm 报名方式:区域预赛一般每年9-1…...
Metasploit入门到高级【第九章】
预计更新第一章:Metasploit 简介 Metasploit 是什么Metasploit 的历史和发展Metasploit 的组成部分 第二章:Kali Linux 入门 Kali Linux 简介Kali Linux 安装和配置常用命令和工具介绍 第三章:Metasploit 基础 Metasploit 的基本概念Met…...
JDK之8后: 协程? 虚拟线程!!!
特性官方文档: https://openjdk.org/jeps/436 Java协程 近三十年来,Java 开发人员一直依赖线程作为并发服务器应用程序的构建块。每个方法中的每个语句都在线程内执行,并且由于 Java 是多线程的,因此多个执行线程同时发生。线程是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推荐期刊和会议分享(人工智能)
前 言国内高等院校研究生及博士毕业条件需要发表高水平期刊或者顶会(清北上交等重点学校毕业要求为至少发一篇顶会),很多同学私信问到一级学会的会议论文怎么找、是什么,比如前段时间放榜的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…...
交换瓶子
交换瓶子 贡献者:programmer_ada 有N个瓶子,编号 1 ~ N,放在架子上。 比如有5个瓶子: 2 1 3 5 4 要求每次拿起2个瓶子,交换它们的位置。 经过若干次后,使得瓶子的序号为: 1 2 3 4 5 对于这么…...
Windsurf Cascade报错别慌!手把手教你清理Windows/Mac缓存,亲测有效
Windsurf Cascade报错急救指南:双平台缓存清理与实战避坑 刚写完的代码突然被Cascade error打断?别急着砸键盘。作为每天与Windsurf相伴12小时的深度用户,我经历过数十次这类报错——从最初的暴躁摔鼠标到现在的30秒快速修复,这套…...
不止是上网:用PVE虚拟的OpenWRT旁路由解锁Docker、AdGuard Home和异地组网玩法
解锁PVE虚拟OpenWRT旁路由的进阶玩法:从Docker到智能家居中枢 在家庭网络架构中,OpenWRT旁路由早已超越了简单的网关转发角色。当它运行在PVE虚拟化环境中时,这个轻量级Linux系统(仅需1G内存)可以变身为多功能家庭网络…...
OpCore Simplify:三步搞定黑苹果EFI配置的智能工具
OpCore Simplify:三步搞定黑苹果EFI配置的智能工具 【免费下载链接】OpCore-Simplify A tool designed to simplify the creation of OpenCore EFI 项目地址: https://gitcode.com/GitHub_Trending/op/OpCore-Simplify 还在为黑苹果的复杂EFI配置而烦恼吗&am…...
Altium Designer新手必看:5分钟搞定PCB封装库创建(附3D模型导入技巧)
Altium Designer新手实战:从零构建PCB封装库与3D模型高效导入 刚接触Altium Designer的工程师常被PCB封装库的创建难住——焊盘尺寸怎么定?丝印如何对齐?3D模型能否可视化验证?这些问题直接关系到后期PCB设计的成功率。本文将用最…...
OpenClaw夜间任务优化:Qwen3-32B+RTX4090D镜像低负载模式配置
OpenClaw夜间任务优化:Qwen3-32BRTX4090D镜像低负载模式配置 1. 问题背景与优化动机 去年12月,我开始用OpenClawQwen3-32B模型搭建个人自动化工作流。最初配置的定时备份任务每晚11点准时运行,但很快发现两个问题: 电费异常&am…...
【全场景优化】WaveTools鸣潮性能调校指南:从卡顿到流畅的完整解决方案
【全场景优化】WaveTools鸣潮性能调校指南:从卡顿到流畅的完整解决方案 【免费下载链接】WaveTools 🧰鸣潮工具箱 项目地址: https://gitcode.com/gh_mirrors/wa/WaveTools 问题定位:硬件与软件的兼容性挑战 当代游戏性能优化面临的核…...
全志T3核心板DDR初始化失败:从ZQ校准误导到VREF电压偏差的排查实录
1. 问题现象与初步排查 那天早上刚到实验室,测试组的同事就急匆匆跑过来:"哥,又有三台设备启动不了,uboot都没跑起来!"我接过设备一看,果然又是熟悉的ZQ校准错误提示,这已经是本周第五…...
Guohua Diffusion 快速入门:三步完成星图GPU平台一键部署
Guohua Diffusion 快速入门:三步完成星图GPU平台一键部署 想试试AI绘画,但被复杂的安装和环境配置劝退?今天,咱们就来聊聊怎么用最简单的方式,在星图GPU平台上玩转Guohua Diffusion。整个过程,你只需要点三…...
从零到一:在Simulink中构建SVPWM仿真模型的实践指南
1. 为什么选择Simulink搭建SVPWM模型? 第一次接触电机控制时,我被各种专业术语搞得晕头转向。直到发现Simulink这个可视化工具,才真正理解了SVPWM(空间矢量脉宽调制)的精髓。就像用乐高积木搭建城堡,Simuli…...
组态王Modbus高低字节调整实战:3种方法解决数据乱跳问题(附modbusmaster.ini配置)
组态王Modbus高低字节调整实战:3种方法解决数据乱跳问题(附modbusmaster.ini配置) 工业现场的数据通讯就像一场精密的外科手术,任何一个字节的错位都可能导致整个系统"瘫痪"。最近在调试某化工厂DCS系统时,遇…...

