本文共 1076 字，大约阅读时间需要 3 分钟。

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 31 2

Sample Output

3

分析&说明：

这道题是求最少步数，自然就用 广搜啦。要改导航变为马的走法，然后就是模板啦。

代码：

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;struct node{   	int x,y,step;}que[5001];int dx[10] = {   2,1,-1,-2,-2,-1,1,2};int dy[10] = {   1,2,2,1,-1,-2,-2,-1};  //改导航int n,m,ex,ey,best//存储最优解;void bfs(){   	int head=1,tail=1;	que[1].x=1;que[1].y=1;	que[1].step=0;	tail++;	while(head
       
        0&&yy<=n&&yy>0)			{   				que[tail].x=xx;				que[tail].y=yy;				que[tail].step=que[head].step+1;				tail++;				if(xx==ex&&yy==ey)				{   					best=que[tail-1].step;					return;  //很重要 不然会炸				}			}		}		head++;	}}int main(){   	cin>>n>>m>>ex>>ey;	bfs();	if(best==0) cout<<"NEVER";  //无解	else cout<