当前位置:网站首页>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
边栏推荐
- CAIP2021 初赛VP
- STL标准模板库(Standard Template Library)一周学习总结
- Dynamics 365 查找字段过滤
- LDO voltage stabilizing chip - internal block diagram and selection parameters
- VS扩展工具笔记
- 统计电影票房排名前10的电影并存入还有一个文件
- Wechat forum exchange applet system graduation design completion (8) graduation design thesis template
- 伸展树(一) - 图文解析与C语言实现
- LDO穩壓芯片-內部框圖及選型參數
- 移动端异构运算技术 - GPU OpenCL 编程(基础篇)
猜你喜欢
生鲜行业数字化采购管理系统:助力生鲜企业解决采购难题,全程线上化采购执行
[microservices SCG] gateway integration Sentinel
【编译原理】词法分析设计实现
Cloud native is devouring everything. How should developers deal with it?
Installing spss25
Puce à tension stabilisée LDO - schéma de bloc interne et paramètres de sélection du modèle
Wechat forum exchange applet system graduation design completion (1) development outline
14、 Two methods of database export and import
ROS2专题(03):ROS1和ROS2的区别【02】
十三、系统优化
随机推荐
Matlab 信号处理【问答随笔·2】
Adults have only one main job, but they have to pay a price. I was persuaded to step back by personnel, and I cried all night
Adrnoid开发系列(二十五):使用AlertDialog创建各种类型的对话框
ArcGIS: field assignment_ The attribute table field calculator assigns values to fields based on conditions
Why does the market need low code?
Solution: prompt "unsupported video format" when inserting avi format video into the message
CAIP2021 初赛VP
Network security -burpsuit
Unity3D学习笔记5——创建子Mesh
Oracle database backup and recovery
Inftnews | web5 vs Web3: the future is a process, not a destination
LeeCode -- 6. Z 字形变换
Two kinds of curves in embedded audio development
The 19th Zhejiang Provincial Collegiate Programming Contest 2022浙江省赛 F.EasyFix 主席树
1. Sum of two numbers
Inftnews | the wide application of NFT technology and its existing problems
Network security - joint query injection
VS扩展工具笔记
Wechat forum exchange applet system graduation design (2) applet function
Happy gathering time