-骑士巡游-

题目描述

马在中国象棋以日字形规则移动，给定n*m大小的棋盘，以及马的初始位置(x，y)和目标位置（s，t），要求不能重复经过棋盘上的同一个点，计算马至少走多少步可以到达目标位置，所有棋盘保证从初始位置到结束位置一定有路径可达。

输入

测试数据包含一行，为六个整数，分别为棋盘的大小以及初始位置坐标nmxyst。（1≤x，s≤n≤5，1≤y，t≤m≤5）

输出

包含一行，为一个整数，表示马能到达目标位置的最小步数。

样例输入

3 3 1 1 1 3

样例输出

2

参考代码：

#include<bits/stdc++.h>
using namespace std;
int n,m;
int q[5000][2],x,y,s,t,hh,tt,kx,ky,l,gx,gy;
int dx[]={1,1,-1,-1,2,2,-2,-2};
int dy[]={2,-2,2,-2,1,-1,1,-1};
int d[50][50];
void bfs(){
    while(hh!=tt){
        kx=q[hh][1];
        ky=q[hh][0];
        hh++;
        for(int i=0;i<8;i++){
            int xx=kx+dx[i];
            int yy=ky+dy[i];
            if(xx>=0&&xx<m&&yy>=0&&yy<n&&d[yy][xx]==0){
                tt++;
                q[tt-1][0]=yy;
                q[tt-1][1]=xx;
                d[yy][xx]=d[ky][kx]+1;
            }
        }
    }
    return;
}
int main(){
    cin>>n>>m>>y>>x>>t>>s;
    tt++;
    d[y][x]=1;
    q[0][1]=x-1;
    q[0][0]=y-1;
    bfs();
    cout<<d[t-1][s-1];
    return 0;
}