当前位置:网站首页>First week of July
First week of July
2022-07-07 23:25:00 【zjsru_ Beginner】
The knight moves
Title Description : Write program , Calculate the minimum number of times the knight needs to move from one position to another . The rules of Knight movement are as follows .
Every beat , There are eight choices , After many correct choices, you can find a nearest journey .
Algorithm design :
This is a problem of finding the shortest distance , have access to queue Perform breadth first search steps , Now put the starting point in the queue , If the queue is not empty , Then the right head out of the right , Otherwise, expand 8 A direction , If you find a target , Then the step size is returned immediately +1 And put it in the queue , Mark it as visited , If the knight's current position is (x,y), Then the current position coordinate plus the offset when moving .
Input :
3
8
0 0
7 0
100
0 0
30 50
10
1 1
1 1
Output :
5
28
0
Code :
#include<bits/stdc++.h>
int size ;
struct status{ # Structure
int x;
int y;
int step;
}q[100006];
int vec[8][2]={
{-2,-1},{-1,-2},{-2,1},{-1,2},{2,-1},{1,-2},{2,1},{1,2}}; # Direction
int is[333][333];
void bfs(int sx,int sy,int ex,int ey){ # Breadth first search
int head =0,tail=0;
memset(is,0,sizeof(is));
q[tail].x=sx;
q[tail].y=sy;
is[sx][sy]=1;
tail++;
while (head<tail){
if (q[head].x==ex&&q[head].y==ey){
printf("%d\n",q[head].step);
break ;
}
for(int i=0;i<8;i++){ # Traverse all directions
int nx=q[head].x+vec[i][0];
int ny=q[head].y+vec[i][1];
int step=q[head].step;
if (nx>=0&&nx<size&&ny>=0&&ny<size&&is[nx][ny]==0){
q[tail].x=nx;
q[tail].y=ny;
q[tail].step=step+1;
is[nx][ny]=1;
tail++;
}
}
head ++;
}
}
int main(){
int k;
scanf("%d",&k);
int sx,sy,ex,ey;
while (k--){ # Traverse each target to achieve the shortest distance
scanf("%d",&size);
scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
bfs(sx,sy,ex,ey);
}
return 0;
}
YJG
边栏推荐
猜你喜欢
Cloud native is devouring everything. How should developers deal with it?
leetcode-520. Detect capital letters -js
移动端异构运算技术 - GPU OpenCL 编程(基础篇)
Technology at home and abroad people "see" the future of audio and video technology
Wechat forum exchange applet system graduation design (2) applet function
Talk about the design and implementation logic of payment process
Wechat forum exchange applet system graduation design completion (8) graduation design thesis template
PMP project management exam pass Formula-1
伸展树(一) - 图文解析与C语言实现
Unity3D学习笔记6——GPU实例化(1)
随机推荐
LeeCode -- 6. Zigzag transformation
windows设置redis开启自动启动
14、 Two methods of database export and import
PMP项目管理考试过关口诀-1
STL标准模板库(Standard Template Library)一周学习总结
给出一个数组,如 [7864, 284, 347, 7732, 8498],现在需要将数组中的数字拼接起来,返回「最大的可能拼出的数字」
CXF call reports an error. Could not find conduct initiator for address:
Turbo introder common scripts
Technology at home and abroad people "see" the future of audio and video technology
系统架构设计师备考经验分享:论文出题方向
ROS2专题(03):ROS1和ROS2的区别【02】
Adrnoid开发系列(二十五):使用AlertDialog创建各种类型的对话框
Wechat forum exchange applet system graduation design (2) applet function
MySQL Index Optimization Practice I
十三、系统优化
Two kinds of curves in embedded audio development
漏洞复现----49、Apache Airflow 身份验证绕过 (CVE-2020-17526)
Grid
Count the top 10 films at the box office and save them in another file
PCI-Express接口的PCB布线规则