1257：Knight Moves

传送门：http://ybt.ssoier.cn:8088/problem_show.php?pid=1257

 

【题目描述】

输入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

#include<iostream>
#include<queue>
#include<cstring>
using namespace std; 
#define N 300+1
struct node{
    int x,y,t;
};
int sx,sy,ex,ey,l,t;
int xs[]={1,1,-1,-1,2,2,-2,-2};
int ys[]={2,-2,2,-2,1,-1,1,-1};
bool maps[N][N];
void bfs()
{
    queue<node>q;
    node st;
    st.x=sx;
    st.y=sy;
    st.t=0;
    q.push(st);
    while(!q.empty())
    {
        node nt=q.front();q.pop();
        if(nt.x==ex&&nt.y==ey)
        {
            cout<<nt.t<<endl;
            break;
        }
        for(int i=0;i<8;i++)
        {
            int x=nt.x+xs[i];
            int y=nt.y+ys[i];
            if(maps[x][y]==true&&x>=0&&x<l&&y>=0&&y<l)
            {
                maps[x][y]=false;
                node tmp;
                tmp.x=x;
                tmp.y=y;
                tmp.t=nt.t+1;
                q.push(tmp);
            }
        }
    }
    return ;
}
int main()
{
    cin>>t;
    while(t--)
    {
        memset(maps,true,sizeof(maps));
        cin>>l;
        cin>>sx>>sy>>ex>>ey;
        maps[sx][sy]=false;
        bfs();
    }
}