题目描述

输入n代表有个n×n的棋盘，输入开始位置的坐标和结束位置的坐标，问一个骑士朝棋盘的八个方向走马字步，从开始坐标到结束坐标可以经过多少步。

【输入】
首先输入一个n,表示测试样例的个数。

每个测试样例有三行。

第一行是棋盘的大小L(4≤L≤300)；

第二行和第三行分别表示马的起始位置和目标位置(0..L−1)。

【输出】
马移动的最小步数，起始位置和目标位置相同时输出0。

样例

【输入样例】
3
8
0 0
7 0
100
0 0
30 50
10
1 1
1 1
【输出样例】
5
28
0

这道题属于bfs迷宫问题的分叉：马走日，主要要写好方向数组，如果方向数组写错了，那答案肯定是错的

C++ 代码

#include<bits/stdc++.h>
using namespace std;
int dx[]={1,1,-1,-1,2,2,-2,-2};     
int dy[]={2,-2,2,-2,1,-1,1,-1};
struct node{
    int x;
    int y;
    int step;
};
bool vis[1005][1005];
int main(){
    int n;
    cin>>n;
    int big;
    int nx,ny,mx,my;
    for(int i=0;i<n;i++){
        memset(vis,false,sizeof(vis));
        cin>>big>>nx>>ny>>mx>>my;
        node start;
        start.x=nx;
        start.y=ny;
        start.step=0;
        queue<node> a;
        a.push(start);
        vis[nx][ny]=true;
        while(!a.empty()){
            node cmp=a.front();
            if(cmp.x==mx && cmp.y==my)
            {
                cout<<cmp.step<<endl;
                break;
            }
                for(int i=0;i<8;i++){
                    int kx=cmp.x+dx[i];
                    int ky=cmp.y+dy[i];
                    if(vis[kx][ky]==false && kx>=0 && kx<big && ky>=0 && ky<big)
                    {
                        vis[kx][ky]=true;
                        node tmp;
                        tmp.x=kx;
                        tmp.y=ky;
                        tmp.step=cmp.step+1;
                        a.push(tmp);
                    }
            }
             a.pop();
        }

    }
    return 0;
}