骑士旅行

Description
在一个n m 格子的棋盘上，有一只国际象棋的骑士在棋盘的左下角 (1;1)(如图1)，骑士只能根据象棋的规则进行移动，要么横向跳动一格纵向跳动两格，要么纵向跳动一格横向跳动两格。 例如， n=4，m=3 时，若骑士在格子(2;1) (如图2), 则骑士只能移入下面格子：(1;3),(3;3) 或 (4;2)；对于给定正整数n，m，I，j值 (m,n<=50,I<=n,j<=m) ，你要测算出从初始位置(1;1) 到格子(i;j)最少需要多少次移动。如果不可能到达目标位置，则输出"NEVER"。

Input
输入文件的第一行为两个整数n与m，第二行为两个整数i与j。

Output
输出文件仅包含一个整数为初始位置(1;1) 到格子(i;j)最少移动次数。

Sample Input
5 3
1 2

Sample Output
3

分析
这题我们可以用广搜（BFS）
我们可以逐步求出到每一个点的最少移动次数，然后目标位置的值就是从（1,1）到（i,j）的最少移动次数

AC代码

#include<iostream>
using namespace std;
int dx[9]={
   0,2,2,-2,-2,1,1,-1,-1};//8个方向延伸
int dy[9]={
   0,1,-1,1,-1,2,-2,2,-2};
int n,m,x1,y1,num,head,tail,st[2505][4],a[1005][1005];
bool check(int x,int y)//判断边界和是否踩过
{
   
	if(x>=1&&x<=n&&y>=1&&y<=m&&a[x][y]==0) return true;
	return false;
}
void bfs()
{
   
	tail++;
	a[1][1]=1;
	st[1][1]=1;st[1][2]=1;st[1][3]=0;//初始值
	do
	{
   
		head++;
		for(int i=1;i<=8;i++)//遍历8个方向
		 if(check(st[head][1]+dx[i],st[head][2]+dy[i]))
		 {
   
		 	tail++;
		 	st[tail][1]=st[head][1]+dx[i];st[tail][2]=st[head][2]+dy[i];//更新坐标
		 	st[tail][3]=st[head][3]+1;//次数加1
		 	a[st[tail][1]][st[tail][2]]=1;//出现过
		 	if(st[tail][1]==x1&&st[tail][2]==y1)//是目标位置就输出并退出
		 	{
   
		 		cout<<st[tail][3];
		 		num=1;
		 		return;
		 	}
		 }
	}while(head<=tail);
}
int main()
{
   
	cin>>n>>m>>x1>>y1;
	bfs();
	if(num==0) cout<<"NEVER";//还有其他情况
}

谢谢观看