当前位置:网站首页>1330: [example 8.3] minimum steps
1330: [example 8.3] minimum steps
2022-07-05 15:03:00 【A program ape who beats the keyboard violently】
1330:【 example 8.3】 Minimum steps
The time limit : 1000 ms Memory limit : 65536 KB
Submission number : 13863 Passing number : 7606
【 Title Description 】
In all kinds of chess , The way a piece moves is always certain , For example, in Chinese chess, the horse walks “ Japan ”. One primary school student thought that if a horse could walk in two ways, it would be more interesting , therefore , He stipulated that the horse can press “ Japan ” go , You can walk like an elephant “ field ” word . His deskmate usually likes to play go , It's interesting to know this later , Just want to try , In a (100×100) Choose any two points on your Go board A、B,A Point on the sunspot ,B Point on the white , For two horses . Chess pieces can be pressed “ Japan ” Word walk , You can also press “ field ” Word walk , Two people walk on a dark horse , A white horse . Who walks to the upper left corner with the least number of steps? The coordinate is (1,1) At the same time , Who wins . Now he asks you for help , Here you are. A、B The coordinates of two points , Want to know two positions to (1,1) Point to the minimum number of possible steps .
【 Input 】
A、B The coordinates of two points .
【 Output 】
Minimum steps .
【 sample input 】
12 16
18 10
【 sample output 】
8
9
【 Algorithm analysis 】
because A、B Two points are input randomly , Therefore, the mathematical law of calculating the minimum number of steps cannot be found , It can only be solved by breadth first search .
(1) Determine the starting point
from (n,m) Start with a breadth first search , Can be found from (n,m) The minimum number of steps to all reachable points on the chessboard . What is required in the question is the dark horse (x1,yy1) And white horse (x2,y2) arrive (1,1) The minimum number of steps of the target point . Although the starting points of the two paths are different , But their destination is the same . If we will end (1,1) As a starting point , In this way, you only need one breadth first search to get (x1,yy1) and (x2,y2) arrive (1,1) The minimum number of steps .
(2) data structure
set up queue—— queue , Storage slave (1,1) Reachable point (queue[k][1..2]) And the minimum number of steps required to reach this point (queue[k][3])(0k192+1). The first pointer of the queue is head, The tail pointer is tail. At the beginning ,queue Only one element in the is (1,1), The minimum number of steps is 0.
a—— Record (1,1) The minimum number of steps required to reach each point . obviously , The answer is a[x1][yy1] and a[x2][y2]. At the beginning ,a[1][1] by 0, All other element values are set to -1.
dx、dy—— Position increment array after moving . Ma you 12 Different expansion directions :
Horse walk “ Japan ”:
(n-2,m-1)(n-1,m-2)(n-2,m+1)(n-1,m+2)(n+2,m-1)(n+1,m-2)(n+2,m+1)(n+1,m+2)
Horse walk “ field ”:
(n-2,m-2)(n-2,m+2)(n+2,m-2)(n+2,m+2)
We will i The position increment in the direction is stored in the constant array dx[i]、dy[i] in (0i11):
int dx[12]={-1,-1,-1,1,2,2,2,2,1,-1,-2,-2},dy[12]={-1,-2,-2,-2,-2,-1,1,2,2,2,2,1};
(3) constraint condition
(1) Don't go beyond the boundary . Because of all possible footholds of horses a Both in a Within the scope of , So once the horse goes out of bounds , Just put it a The value assigned to 0, Express “ Has been extended , And (1,1) It takes at least 0 Step ”. This seems absurd , But it can simply and effectively prevent the horse from falling into these boundary points again .
(2) This point has not been reached in previous extensions . If you have ever arrived , According to the principle of breadth first search , The number of steps required to reach this point previously must be less than the current number of steps , Therefore, there is absolutely no need to expand .
The resulting , The position of the horse after jumping (n,m) The constraint of whether you can join the team is a[n][m]0.
(4) Algorithm flow
【AC Code 】
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<string>
#include<vector>
using namespace std;
const int N=1e3+10;
inline int fread()
{
char ch=getchar();
int n=0,m=1;
while(ch<'0' or ch>'9')
{
if(ch=='-')m=-1;
ch=getchar();
}
while(ch>='0' and ch<='9')n=(n<<3)+(n<<1)+ch-48,ch=getchar();
return n*m;
}
int dx[12]={-1,-1,-1,1,2,2,2,2,1,-1,-2,-2},dy[12]={-1,-2,-2,-2,-2,-1,1,2,2,2,2,1},a[N][N],q[10000][4],x1,yy1,x2,y2,head=1,tail=1;// Initial position join the team
signed main()
{
memset(a,0xff,sizeof a),q[1][1]=q[1][2]=1,q[1][3]=0,x1=fread(),yy1=fread(),x2=fread(),y2=fread();//a Initialization of an array , Read the starting positions of black and white horses
while(head<=tail)
{
for(int i=0;i<12;i++)// enumeration 12 Expansion directions
{
int n=q[head][1]+dx[i],m=q[head][2]+dy[i];// Calculate Horse Press i Position after direction jump
if(n>0 and m>0)
if(a[n][m]==-1)// if (n,m) Meet the constraints
{
a[n][m]=q[head][3]+1,tail++,q[tail][1]=n,q[tail][2]=m,q[tail][3]=a[n][m];// Calculation (1,1) To (n,m) The minimum number of steps ,(1,1) to (n,m) Join the team with the minimum number of steps
if(a[x1][yy1]>0 and a[x2][y2]>0)// Output the solution of the problem
{
cout<<a[x1][yy1]<<"\n";
cout<<a[x2][y2]<<"\n";
return 0;
}
}
}
head++;
}
return 0;
}
I like to use arrays to simulate queues
( It's not because I don't want to remember the queue's operation function ).
边栏推荐
猜你喜欢
Interpretation of Apache linkage parameters in computing middleware
There is a powerful and good-looking language bird editor, which is better than typora and developed by Alibaba
选择排序和冒泡排序
1330:【例8.3】最少步数
Live broadcast preview | how to implement Devops with automatic tools (welfare at the end of the article)
Ctfshow web entry command execution
Crud de MySQL
How to paste the contents copied by the computer into mobaxterm? How to copy and paste
Thymeleaf uses background custom tool classes to process text
Machine learning notes - gray wolf optimization
随机推荐
Dark horse programmer - software testing -10 stage 2-linux and database -44-57 why learn database, description of database classification relational database, description of Navicat operation data, de
FR练习题目---综合题
CPU design related notes
危机重重下的企业发展,数字化转型到底是不是企业未来救星
leetcode:881. lifeboat
GPS原始坐标转百度地图坐标(纯C代码)
PyTorch二分类时BCELoss,CrossEntropyLoss,Sigmoid等的选择和使用
PostgreSQL 13 installation
729. 我的日程安排表 I :「模拟」&「线段树(动态开点)」&「分块 + 位运算(分桶)」
MySQL----函数
Photoshop插件-动作相关概念-ActionList-ActionDescriptor-ActionList-动作执行加载调用删除-PS插件开发
be careful! Software supply chain security challenges continue to escalate
华为哈勃化身硬科技IPO收割机
外盘入金都不是对公转吗,那怎么保障安全?
Shanghai under layoffs
Brief introduction of machine learning framework
面试突击62:group by 有哪些注意事项?
基于TI DRV10970驱动直流无刷电机
[12 classic written questions of array and advanced pointer] these questions meet all your illusions about array and pointer, come on!
Differences between IPv6 and IPv4 three departments including the office of network information technology promote IPv6 scale deployment