openjudge_2.5基本算法之搜索_917:Knight Moves

题目

917:Knight Moves
总时间限制: 1000ms 内存限制: 65536kB
描述
Background
Mr Somurolov, fabulous chess-gamer indeed, asserts that no one else but him can move knights from one position to another so fast. Can you beat him?
The Problem
Your task is to write a program to calculate the minimum number of moves needed for a knight to reach one point from another, so that you have the chance to be faster than Somurolov.
For people not familiar with chess, the possible knight moves are shown in Figure 1.
在这里插入图片描述

输入
The input begins with the number n of scenarios on a single line by itself.
Next follow n scenarios. Each scenario consists of three lines containing integer numbers. The first line specifies the length l of a side of the chess board (4 <= l <= 300). The entire board has size l * l. The second and third line contain pair of integers {0, …, l-1}*{0, …, l-1} specifying the starting and ending position of the knight on the board. The integers are separated by a single blank. You can assume that the positions are valid positions on the chess board of that scenario.
输出
For each scenario of the input you have to calculate the minimal amount of knight moves which are necessary to move from the starting point to the ending point. If starting point and ending point are equal,distance is zero. The distance must be written on a single line.
样例输入
3
8
0 0
7 0
100
0 0
30 50
10
1 1
1 1
样例输出
5
28
0

翻译

题目:移动骑士
背景:
Somurov先生,确实是一位出色的国际象棋棋手,声称除了他之外,没有人能如此迅速地将骑士从一个位置移动到另一个位置。你能打败他吗?
问题:
你的任务是编写一个程序来计算骑士从一个点到另一个点所需的最小移动次数,这样你就有机会比索穆罗洛夫更快。
对于不熟悉国际象棋的人来说,可能的骑士招式如图1所示。
输入:
输入以单行上的场景数n开始。
接下来是n个场景。每个场景由包含整数的三行组成。第一行指定棋盘一侧的长度l(4<=l<=300)。整个棋盘的大小为ll。
第二行和第三行包含一对整数{0,…,l-1}
{0,…,l-1},指定骑士在棋盘上的起始和结束位置。整数由一个空格分隔。
您可以假设这些位置是该场景棋盘上的有效位置。
输出:
对于输入的每个场景,您必须计算从起点移动到终点所需的骑士移动的最小数量。如果起点和终点相等,则距离为零。距离必须写在一行上。

理解

1.出发点到目的地的最短距离。用宽搜撒一次就搞定
2.深搜就得回溯尝试所有的线路。

代码

#include <bits/stdc++.h>
//#include <windows.h>
using namespace std;
struct point{
int x,y,t;
}o,p[310][310];
int n,w,
sx,sy,
ex,ey,
d[8][2]={{-1,-2},{-2,-1},{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2}};
void view(){
cout<<“地图”<<endl;
cout<<“列:\t”;for(int j=1;j<=w;j++)cout<<j<<“\t”;cout<<endl;
for(int i=1;i<=w;i++){
cout<<i<<“行\t”;
for(int j=1;j<=w;j++)cout<<p[i][j].t<<“\t”;
cout<<endl;
}
//Sleep(2000);
}
int main(){
//freopen(“data.cpp”,“r”,stdin);
cin>>n;
while(n–){
queue q;
cin>>w>>sx>>sy>>ex>>ey;
for(int i=1;i<=w;i++)
for(int j=1;j<=w;j++)p[i][j]=point{i,j,0};
//view();
p[sx+1][sy+1].t=1;
q.push(point{sx+1,sy+1,0});
int x,y;
while(!q.empty()){
o=q.front();q.pop();
//cout<<“出发:”<<o.x<<“,”<<o.y<<“=”<<o.t<<endl;
if(o.xex+1&&o.yey+1){
cout<<o.t<<endl;break;
}
for(int i=0;i<8;i++){
x=o.x+d[i][0],y=o.y+d[i][1];
if(x<1||x>w||y<1||y>w||p[x][y].t)continue;
p[x][y].t=o.t+1;
//cout<<“到达:”<<x<<“,”<<y<<“=”<<p[x][y].t<<endl;
q.push(p[x][y]);
}
//view();
}
}

return 0;

}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/736000.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

利用MSSQL模拟提权

点击星标&#xff0c;即时接收最新推文 本文选自《内网安全攻防&#xff1a;红队之路》 扫描二维码五折购书 利用MSSQL模拟提权 在MS SQL数据库&#xff0c;可以使用EXECUTE AS语句&#xff0c;以其他用户的上下文执行SQL查询。需要注意的是只有明确授予模拟&#xff08;Impers…

线程间通信方式(互斥(互斥锁)与同步(无名信号量、条件变量))

1通信机制&#xff1a;互斥与同步 线程的互斥通过线程的互斥锁完成&#xff1b; 线程的同步通过无名信号量或者条件变量完成。 2 互斥 2.1 何为互斥&#xff1f; 互斥是在多个线程在访问同一个全局变量的时候&#xff0c;先让这个线程争抢锁的资源&#xff0c;那个线程争抢…

学会python——对目录的操作(python实例十)

目录 1、认识Python 2、环境与工具 2.1 python环境 2.2 Visual Studio Code编译 3、遍历当前目录 3.1 代码构思 3.2 代码示例 3.3 运行结果 4、删除目录中的文件 4.1 代码构思 4.2 代码示例 4.3 运行结果 5、总计 1、认识Python Python 是一个高层次的结合了解释性…

Linux-安装及管理程序

目录 一、Linux应用程序基础 1、应用程序与系统命令的关系 2、 典型应用程序的目录结构 3、常见的软件包封装类型 二、RPM包管理工具 1、RPM包管理器 2、RPM软件包 ​3、RPM的命令格式 4、RPM命令的常用选项 5、RPM安装 三、 yum安装 1、yum源介绍 1.1、本地yum源 …

ClosedXML

一、类库介绍 ClosedXML是一个用于读取、操作和写入Excel 2007 (.xlsx, .xlsm)文件的.NET第三方库。它基于OpenXML&#xff0c;但与OpenXML相比&#xff0c;ClosedXML具有更高的性能和更易于使用的API接口。 ClosedXML支持XML文档的解析和生成&#xff0c;可以处理复杂的XML结…

程序员如何高效读代码?

程序员高效读代码的技巧包括以下几点&#xff1a; 明确阅读目的&#xff1a;在开始阅读代码之前&#xff0c;先明确你的阅读目的。是为了理解整个系统的架构&#xff1f;还是为了修复一个具体的bug&#xff1f;或者是为了了解某个功能是如何实现的&#xff1f;明确目的可以帮助…

系统安全设计规范(Word原件)

1.1安全建设原则 1.2 安全管理体系 1.3 安全管理规范 1.4 数据安全保障措施 1.4.1 数据库安全保障 1.4.2 操作系统安全保障 1.4.3 病毒防治 1.5安全保障措施 1.5.1实名认证保障 1.5.2 接口安全保障 1.5.3 加密传输保障 1.5.4终端安全保障 资料获取&#xff1a;私信或者进主页。…

示例:WPF中推荐一个支持折叠展开的GridSpliter自定义控件GridSplitterBox

一、目的&#xff1a;推荐一个支持折叠展开的GridSpliter自定义控件GridSplitterBox 二、效果 实现功能&#xff1a;设置菜单显示位置&#xff0c;最小宽度&#xff0c;最大宽度&#xff0c;位置持久化保存 三、环境 VS2022 Net7 四、使用方式 1、安装nuget包&#xff1a;H…

能理解你的意图的自动化采集工具——AI和爬虫相结合

⭐️我叫忆_恒心&#xff0c;一名喜欢书写博客的研究生&#x1f468;‍&#x1f393;。 如果觉得本文能帮到您&#xff0c;麻烦点个赞&#x1f44d;呗&#xff01; 近期会不断在专栏里进行更新讲解博客~~~ 有什么问题的小伙伴 欢迎留言提问欧&#xff0c;喜欢的小伙伴给个三连支…

pytest测试框架flaky插件重试失败用例

Pytest提供了丰富的插件来扩展其功能&#xff0c;本章介绍下插件flaky &#xff0c;用于在测试用例失败时自动重新运行这些测试用例。与前面文章介绍的插件pytest-rerunfailures功能有些类似&#xff0c;但是功能上不如pytest-rerunfailures插件丰富。 flaky官方并没有明确pyt…

中国企业数字化转型现状、趋势和挑战

一、来自不同行业、不同所有制的145家企业的调查 为了了解中国企业数字化转型的现状、趋势和挑战&#xff0c;2022年我们完成了一次在线问卷调查。 受访企业达145家&#xff0c;国内企业111家&#xff0c;占比77%&#xff08;其中央企占总比例51%&#xff09;&#xff0c;民营…

【Python机器学习】k均值聚类——矢量量化,或者将k均值看作分解

虽然k均值是一种聚类算法&#xff0c;但在k均值和分解方法之间存在一些相似之处。k均值尝试利用簇中心来表示每个数据点&#xff0c;可以看作仅用一个分量来表示每个数据点&#xff0c;该分量由簇中心给出。这种观点将k均值看作是一种分解方法&#xff0c;其中每个点用单一分量…

【计算机组成原理】部分题目汇总

计算机组成原理 部分题目汇总 一. 简答题 RISC和CICS 简要说明&#xff0c;比较异同 RISC&#xff08;精简指令集&#xff09;注重简单快速的指令执行&#xff0c;使用少量通用寄存器&#xff0c;固定长度指令&#xff0c;优化硬件性能&#xff0c;依赖软件&#xff08;如编译…

Adobe Acrobat 编辑器软件下载安装,Acrobat 轻松编辑和管理各种PDF文件

Adobe Acrobat&#xff0c;它凭借卓越的功能和丰富的工具&#xff0c;为用户提供了一个全面的解决方案&#xff0c;用于查看、创建、编辑和管理各种PDF文件。 作为一款专业的PDF阅读器&#xff0c;Adobe Acrobat能够轻松打开并展示各种格式的PDF文档&#xff0c;无论是文字、图…

软考初级网络管理员__软件单选题

1.在Excel 中&#xff0c;设单元格F1的值为56.323&#xff0c;若在单元格F2中输入公式"TEXT(F1,"&#xffe5;0.00”)”&#xff0c;则单元格F2的值为()。 &#xffe5;56 &#xffe5;56.323 &#xffe5;56.32 &#xffe5;56.00 2.要使Word 能自动提醒英文单…

前沿技术丨S2S自动化测试解决方案

技术背景 随着面向服务的架构&#xff08;Service-Oriented Architecture&#xff0c;SOA&#xff09;在整车架构中的逐步推进及应用&#xff0c;车内网络通信中会一直并存基于以太网的面向服务和基于传统网络的面向信号的两类控制器&#xff0c;S2S&#xff08;Signal to Ser…

USB - USB在消费领域的应用

Switching in USB Consumer Applications 通用串行总线&#xff08;USB&#xff09;已成为满足终端设备之间日益增长的快速数据传输需求的主流接口--例如&#xff0c;在个人电脑和便携式设备&#xff08;如手机、数码相机和个人媒体播放器&#xff09;之间下载和上传数据。 The…

如何与情绪好好相处,真正成为情绪的主人

一、教程描述 若要成为一个聪明的人&#xff0c;就要学会做情绪的主人&#xff0c;而不是被情绪控制自己&#xff0c;为什么要做情绪的主人&#xff1f;至少有以下两个方面原因。 其一&#xff0c;都说&#xff0c;世上还是好人多。可是&#xff0c;为什么你身边没有一个好人…

npm 安装踩坑

1 网络正常&#xff0c;但是以前的老项目安装依赖一直卡住无法安装&#xff1f;哪怕切换成淘宝镜像 解决办法&#xff1a;切换成yarn (1) npm i yarn -g(2) yarn init(3) yarn install在安装的过程中发现&#xff1a; [2/4] Fetching packages... error marked11.1.0:…

android 彩虹进度条自定义view实现

实现一个彩虹色进度条功能&#xff0c;不说明具体用途大家应该能猜到。想找别人造的轮子&#xff0c;但是没有合适的&#xff0c;所以决定自己实现一个。 相关知识 android 自定义view LinearGradient 线性渐变 实现步骤 自定义view 自定义一个TmcView类继承View 重写两…