【洛谷 P1443】马的遍历 题解(广度优先搜索)
马的遍历
题目描述
有一个 n×mn \times mn×m 的棋盘,在某个点 (x,y)(x, y)(x,y) 上有一个马,要求你计算出马到达棋盘上任意一个点最少要走几步。
输入格式
输入只有一行四个整数,分别为 n,m,x,yn, m, x, yn,m,x,y。
输出格式
一个 n×mn \times mn×m 的矩阵,代表马到达某个点最少要走几步(不能到达则输出 −1-1−1)。
样例 #1
样例输入 #1
3 3 1 1
样例输出 #1
0 3 2
3 -1 1
2 1 4
提示
数据规模与约定
对于全部的测试点,保证 1≤x≤n≤4001 \leq x \leq n \leq 4001≤x≤n≤400,1≤y≤m≤4001 \leq y \leq m \leq 4001≤y≤m≤400。
思路
- 马走“日”
- 输出格式:域宽为5,左对齐
- 注意判断是否越界
AC代码
#include <iostream>
#include <queue>
#include <cstring>
#define AUTHOR "HEX9CF"
using namespace std;const int maxn = 405;
const int sun[8][2] = {-2, 1, -2, -1, -1, 2, -1, -2, 2, 1, 2, -1, 1, 2, 1, -2};
int n, m, x, y;bool vis[maxn][maxn];
int stp[maxn][maxn];
queue<pair<int, int>> q;void bfs(int x, int y)
{vis[x][y] = 1;stp[x][y] = 0;q.push(make_pair(x, y));while (!q.empty()){pair<int, int> f = q.front();q.pop();for (int i = 0; i < 8; i++){int xx = f.first + sun[i][0];int yy = f.second + sun[i][1];if (xx > 0 && xx <= n && yy > 0 && yy <= m && !vis[xx][yy]){vis[xx][yy] = 1;q.push(make_pair(xx, yy));stp[xx][yy] = stp[f.first][f.second] + 1;}}}
}int main()
{memset(vis, 0, sizeof(vis));memset(stp, -1, sizeof(stp));cin >> n >> m >> x >> y;stp[x][y] = 0;vis[x][y] = true;q.push(make_pair(x, y));bfs(x, y);for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){printf("%-5d", stp[i][j]);}putchar('\n');}return 0;
}
相关文章:
【洛谷 P1443】马的遍历 题解(广度优先搜索)
马的遍历 题目描述 有一个 nmn \times mnm 的棋盘,在某个点 (x,y)(x, y)(x,y) 上有一个马,要求你计算出马到达棋盘上任意一个点最少要走几步。 输入格式 输入只有一行四个整数,分别为 n,m,x,yn, m, x, yn,m,x,y。 输出格式 一个 nmn \t…...
为什么gpt输出有随机性?
以下答案由chatGPT产生! 为什么gpt输出有随机性? GPT(Generative Pre-trained Transformer)是一种基于Transformer架构的神经语言模型,它是一个深度学习模型,通过在大规模文本数据上进行预训练࿰…...
配置Clion用于STM23开发(Makefile)
前言 对于Clion配置STM32开发环境的教程在网上一搜一大堆,但是大部分都是22年之前的,使用的方法都是在STM32CubeMX生成SW4STM32工程。但是在22年不知道哪个版本后,CubeMX已经不再支持生成SW4STM32工程了,这也是我本人遇到的问题。…...
如何在 Istio 中使用 SkyWalking 进行分布式追踪
在云原生应用中,一次请求往往需要经过一系列的 API 或后台服务处理才能完成,这些服务有些是并行的,有些是串行的,而且位于不同的平台或节点。那么如何确定一次调用的经过的服务路径和节点以帮助我们进行问题排查?这时候…...
HBase高手之路1-Hbase简介
文章目录HBase高手之路1-Hbase简介一、什么是HBase1. HBase简介2. HBase的发展过程二、HBase特点1. 海量存储2. 列式存储3. 极易扩展4. 高并发5. 稀疏6. 强一致性读/写7. 自动分块8. 自动RegionServer故障转移9. Hadoop/HDFS集成10. MapReduce11. Java Client API12. Thrift/RE…...
计算机视觉手指甲标注案例
关键点标注是指识别和标注图像或视频中特定的相关点或区域的过程。在机器学习行业,它经常被用来训练计算机视觉模型,以执行诸如物体检测、分割和跟踪等任务。 关键点注释可用于以下应用: 面部关键点检测:识别图像中人脸上的眼睛…...
linux 字符串截取(cut)
-b :以字节为单位进行分割。这些字节位置将忽略多字节字符边界,除非也指定了 -n 标志。 -c :以字符为单位进行分割。 -d :自定义分隔符,默认为制表符。 -f :与-d一起使用,指定显示哪个区域。 -n…...
003+limou+HTML——(3)HTML列表
000、前言 列表是网页常见的一种数据排列方式,在HTMl中列表一共有三种:有序列表、无序列表、定义列表(另外“目录列表dir”和“菜单列表menu”已经在HTML5中被废除了,现在都是使用无序列表ul来替代) 001、有序列表&a…...
设计模式---工厂模式
目录 1. 简单工厂模式 2. 工厂方法模式 1. 简单工厂模式 简单工厂模式(Simple Factory Patterm)又称为静态工厂方法模式(Static Factory Model),它属于类创建型模式。在简单工厂模式中,可以根据参数的不同返回不同类的实例。简单工厂模式专门定义了一…...
C++基础了解-13-C++ 数组
C 数组 一、C 数组 C 支持数组数据结构,它可以存储一个固定大小的相同类型元素的顺序集合。数组是用来存储一系列数据,但它往往被认为是一系列相同类型的变量。 数组的声明并不是声明一个个单独的变量,比如 number0、number1、…、number9…...
ICC2:限制LVT比例
1) 禁用VT 在优化过程用,如果要禁用某种VT可以直接对其使用dont use,如下示例: set_attribute -objects [get_lib_cells *_lvt*/*] -name dont_use -value true 在dont use lib cell的基础上还可以对某些模块放开lvt的使用。 set_app_options -name …...
Kettle工具通过JNDI连接Oracle集群
我们在用Kettle ETL工具的时候,可能会遇到数据库为Oracle集群的模式,或者有时候目标库为oracle,在持续的循环调度中,经常发现oracle的数据库连接中断的情况,此时,在Kettle中有一个JNDI的连接方式能很好的解…...
[ 常用工具篇 ] windows安装phpStudy_v8.1_X64
🍬 博主介绍 👨🎓 博主介绍:大家好,我是 _PowerShell ,很高兴认识大家~ ✨主攻领域:【渗透领域】【数据通信】 【通讯安全】 【web安全】【面试分析】 🎉点赞➕评论➕收藏 养成习…...
SpringBoot 如何将配置文件挂到 jar 包外面?
目录一、SpringBoot 指定配置文件路径:1)使用命令行参数:2)使用环境变量:3)使用外部配置文件:二、SpringBoot 配置文件生效的优先级排序:一、SpringBoot 指定配置文件路径࿱…...
蓝桥杯C/C++b组第一题个人整理合集(5年真题+模拟题)
蓝桥杯C/Cb组填空第一题合集 前言 比赛标准的签到题,比赛时的第一题。不会考到什么算法,甚至都不需要你打代码。但有时候第一题都没做出来的确是非常挫灭信心 看了看历年题目。很多小陷阱也不少 今年的比赛也正好还有一个月,自己对填空题第…...
深入浅出PaddlePaddle函数——paddle.zeros
分类目录:《深入浅出PaddlePaddle函数》总目录 相关文章: 深入浅出PaddlePaddle函数——paddle.Tensor 深入浅出PaddlePaddle函数——paddle.ones 深入浅出PaddlePaddle函数——paddle.zeros 深入浅出PaddlePaddle函数——paddle.full 深入浅出Padd…...
[力扣sql]
题目 表: Person ---------------------- | 列名 | 类型 | ---------------------- | PersonId | int | | FirstName | varchar | | LastName | varchar | ---------------------- personId 是该表的主键列。 该表包含一些人的 ID 和他们的姓和名的信…...
Docker基本操作
目录 Docker基本操作 1、镜像操作 2、容器操作 3、数据卷(容器数据管理) 4、数据卷挂载 5、Dockerfile自定义镜像 Docker基本操作 1、镜像操作 镜像名称一般分两部分组成:[repository]:[tag]。 在没有指定tag时,默认是la…...
golang如何使用rocketmq 附加闭坑指南 建议收藏!!!
文章目录前言一、rocketmq是什么?二、rocketmq核心概念三、rocketmq核心应用四、go如何使用rocketmq总结前言 当我们的业务达到一定规模,很多业务需要解耦,以及需要流量削峰的时候,我们需要使用MQ来让我们系统能够正常运转。 一…...
C++实现的二叉树创建和遍历,超入门邻家小女也懂了
目录 二叉树 特点 性质 二叉树的创建 声明 创建 -> 成员运算符 批量创建 二叉树的遍历 先序遍历 中序遍历 后序遍历 层序遍历 树的相关术语 特殊二叉树 满二叉树 完全二叉树 二叉树 树(Tree)是n(n≥0)个节点的有限集。在任意一棵…...
Spring Boot 实现流式响应(兼容 2.7.x)
在实际开发中,我们可能会遇到一些流式数据处理的场景,比如接收来自上游接口的 Server-Sent Events(SSE) 或 流式 JSON 内容,并将其原样中转给前端页面或客户端。这种情况下,传统的 RestTemplate 缓存机制会…...
汽车生产虚拟实训中的技能提升与生产优化
在制造业蓬勃发展的大背景下,虚拟教学实训宛如一颗璀璨的新星,正发挥着不可或缺且日益凸显的关键作用,源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例,汽车生产线上各类…...
抖音增长新引擎:品融电商,一站式全案代运营领跑者
抖音增长新引擎:品融电商,一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中,品牌如何破浪前行?自建团队成本高、效果难控;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...
2025盘古石杯决赛【手机取证】
前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来,实在找不到,希望有大佬教一下我。 还有就会议时间,我感觉不是图片时间,因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...
今日科技热点速览
🔥 今日科技热点速览 🎮 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售,主打更强图形性能与沉浸式体验,支持多模态交互,受到全球玩家热捧 。 🤖 人工智能持续突破 DeepSeek-R1&…...
使用 SymPy 进行向量和矩阵的高级操作
在科学计算和工程领域,向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能,能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作,并通过具体…...
【电力电子】基于STM32F103C8T6单片机双极性SPWM逆变(硬件篇)
本项目是基于 STM32F103C8T6 微控制器的 SPWM(正弦脉宽调制)电源模块,能够生成可调频率和幅值的正弦波交流电源输出。该项目适用于逆变器、UPS电源、变频器等应用场景。 供电电源 输入电压采集 上图为本设计的电源电路,图中 D1 为二极管, 其目的是防止正负极电源反接, …...
【JVM】Java虚拟机(二)——垃圾回收
目录 一、如何判断对象可以回收 (一)引用计数法 (二)可达性分析算法 二、垃圾回收算法 (一)标记清除 (二)标记整理 (三)复制 (四ÿ…...
无需布线的革命:电力载波技术赋能楼宇自控系统-亚川科技
无需布线的革命:电力载波技术赋能楼宇自控系统 在楼宇自动化领域,传统控制系统依赖复杂的专用通信线路,不仅施工成本高昂,后期维护和扩展也极为不便。电力载波技术(PLC)的突破性应用,彻底改变了…...
Redis——Cluster配置
目录 分片 一、分片的本质与核心价值 二、分片实现方案对比 三、分片算法详解 1. 范围分片(顺序分片) 2. 哈希分片 3. 虚拟槽分片(Redis Cluster 方案) 四、Redis Cluster 分片实践要点 五、经典问题解析 C…...
