骑士出行-题目+答案

题目描述：

国际象棋中的骑士（走日字型），从棋盘上一个点走到另一个点最少需要几步。（起点记作0步）

输入格式：

第一行输入一个整数n,表示棋盘的大小为n∗n,棋盘两个维度的坐标都是从0到n-1

接下来两行,每行两个整数分别表示出发点的坐标与终点的坐标。

输出格式：

输出一个整数，表示最小步数

样例输入：

100 0 0 30 50

样例输出：

28

约定：

1<=3001<=n<=300

接下来看看代码：

#include<bits/stdc++.h>
using namespace std;
int dx[8]={-1,-2,-2,-1,1,2,2,1};
int dy[8]={-2,-1,1,2,2,1,-1,-2};
int n,nx,ny,sx,sy;
int vis[1005][1005];
struct node{
	int x,y,step;
};
void bfs(){
	queue<node>que;
	que.push({nx,ny,0});
	vis[nx][ny]=1;
	while(!que.empty()){
		node head=que.front();que.pop();
		if(head.x==sx and head.y==sy){
			cout<<head.step;
			return;
		}
		for(int i=0;i<8;i++){
			int ax=head.x+dx[i];
			int ay=head.y+dy[i];
			if(ax>=0 and ax<n and ay>=0 and ay<n and vis[ax][ay]==-1){
				vis[ax][ay]=1;
				que.push({ax,ay,head.step+1});
			}
		}
	}
}

int main(){
	memset(vis,-1,sizeof vis);
	cin>>n>>nx>>ny>>sx>>sy;	
	bfs();
}