1. 骑士出行
XJOI - 题目ID：3330必做题100分
时间限制: 200ms
空间限制: 131072kB
题目描述
时间：0.2s 空间：32M
题目描述：
国际象棋中的骑士（走日字型），从棋盘上一个点走到另一个点最少需要几步。（起点记作0步）
[image]
输入格式：
第一行输入一个整数�n,表示棋盘的大小为�∗�n∗n,棋盘两个维度的坐标都是从0到n-1
接下来两行每行两个整数分别表示出发点的坐标与终点的坐标。
输出格式：
输出一个整数，表示最小步数
样例输入：
100 0 0 30 50
样例输出：
28
约定：
1<=�<=3001<=n<=300
#include<bits/stdc++.h>
using namespace std;
struct Box{
int x,y,d;
};
int dx[8]={-1,-2,-2,-1,1,2,2,1};
int dy[8]={-2,-1,1,2,2,1,-1,-2};
int n,sx,sy,fx,fy,vis[305][305];
int dfs(int x,int y)
{
queue<Box> que;
que.push(Box{x,y,0});
vis[x][y]=1;
while(que.size()){
Box hd = que.front();que.pop();
if(hd.x ==fx &&hd.y==fy)return hd.d;
for(int i=0;i<8;i++){
int nx =hd.x+dx[i],ny=hd.y+dy[i];
if(0<=nx&&nx<n&&0<ny&&ny<n&& vis[nx][ny]==0){
que.push(Box{nx,ny,hd.d+1});
vis[nx][ny]=1;
}
}
}
return -1;
}
int main(){
cin>>n;
cin>>sx>>sy>>fx>>fy;
cout<<dfs(sx,sy);
}