当前位置:网站首页>七月第一周
七月第一周
2022-07-07 21:50:00 【zjsru_Beginner】
骑士移动
题目描述:写程序,计算骑士从一个位置移动到另一个位置所需的最少移动次数。骑士移动的规则如下如所示。
每一次跳动,都可以有八种选择,经过多次正确选择后可以找到一个最近的路程。
算法设计:
这是一个求最短距离的问题,可以使用queue进行广度优先搜索步骤,现将起点放入队列,如果队列不空,则对头出对,否则扩展8个方向,如果找到目标,则立即返回步长+1并放入队列,标记其已访问,如果骑士的当前位置为(x,y),则移动时当前位置坐标加上偏移量即可。
输入:
3
8
0 0
7 0
100
0 0
30 50
10
1 1
1 1
输出:
5
28
0
代码:
#include<bits/stdc++.h>
int size ;
struct status{ #结构体
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}}; #方向
int is[333][333];
void bfs(int sx,int sy,int ex,int ey){ #广度优先搜索
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++){ #对各个方向进行遍历
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--){ #对每个要实现最短距离的目标进行遍历
scanf("%d",&size);
scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
bfs(sx,sy,ex,ey);
}
return 0;
}
YJG
边栏推荐
- Understand the session, cookie and token at one time, and the interview questions are all finalized
- ArcGIS:字段赋值_属性表字段计算器(Field Calculator)依据条件为字段赋值
- Binary tree
- ./ setup. Insufficient sh permission
- Years of summary, some core suggestions for learning programming
- Transparent i/o model from beginning to end
- Gee (IV): calculate the correlation between two variables (images) and draw a scatter diagram
- Unity与WebGL的相爱相杀
- Txt file virus
- 小程序多种开发方式对比-跨端?低代码?原生?还是云开发?
猜你喜欢
小程序多种开发方式对比-跨端?低代码?原生?还是云开发?
微信论坛交流小程序系统毕业设计毕设(3)后台功能
Specific method example of V20 frequency converter manual automatic switching (local remote switching)
海内外技术人们“看”音视频技术的未来
14、 Two methods of database export and import
Sword finger offer 27 Image of binary tree
微信论坛交流小程序系统毕业设计毕设(2)小程序功能
Innovation today | five key elements for enterprises to promote innovation
一次搞明白 Session、Cookie、Token,面试问题全稿定
Interview questions: how to test app performance?
随机推荐
线上面试,该如何更好的表现自己?这样做,提高50%通过率~
微信论坛交流小程序系统毕业设计毕设(2)小程序功能
Network security CSRF
What are the similarities and differences between smart communities and smart cities
Gee (III): calculate the correlation coefficient between two bands and the corresponding p value
What is ADC sampling rate (Hz) and how to calculate it
Grid
今日创见|企业促进创新的5大关键要素
Microbial Health Network, How to restore Microbial Communities
微信论坛交流小程序系统毕业设计毕设(6)开题答辩PPT
【刷题记录】3. 无重复字符的最长子串
Some parameters of Haikang IPC
When copying something from the USB flash disk, an error volume error is reported. Please run CHKDSK
Cases of agile innovation and transformation of consumer goods enterprises
leetcode-520. 检测大写字母-js
What is fake sharing after filling the previous hole?
Txt file virus
海内外技术人们“看”音视频技术的未来
This time, let's clear up: synchronous, asynchronous, blocking, non blocking
30讲 线性代数 第五讲 特征值与特征向量