信息学奥赛一本通（1257：Knight Moves）

1257：Knight Moves

时间限制: 1000 ms         内存限制: 65536 KB
提交数: 6149     通过数: 3100

【题目描述】

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

【输入】

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

每个测试样例有三行。

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

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

【输出】

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

【输入样例】

3
8
0 0
7 0
100
0 0
30 50
10
1 1
1 1

【输出样例】

5
28
0

 【分析】

        马走日，8个方向，方向数组(1,2),(1,-2),(-1,2),(-1,-2),(2,1),(2,-1),(-2,1),(-2,-1)。

【参考代码】

#include<iostream>
#include<queue>
#include<cstring>

using namespace std;

const int N=310;

struct node
{
    int x,y;
	int t;
};

int sx,sy;     //起点坐标 
int ex,ey;     //终点坐标 
int l;         //棋盘大小 

int dx[]={1,1,-1,-1,2,2,-2,-2};    //方向数组 
int dy[]={2,-2,2,-2,1,-1,1,-1};

bool vis[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();
        if(nt.x==ex && nt.y==ey)
        {
            cout<<nt.t<<endl;
            break;
        }
        for(int i=0;i<8;i++)
        {
            int nx=nt.x+dx[i];
            int ny=nt.y+dy[i];
            if(vis[nx][ny]==false && nx>=0 && nx<l && ny>=0 && ny<l)
            {
                vis[nx][ny]=true;
                node tmp;
                tmp.x=nx;
                tmp.y=ny;
                tmp.t=nt.t+1;
                q.push(tmp);
            }
        }
        q.pop();
    }
    return;
}
int main()
{
	int t;
    cin>>t;
    while(t--)
    {
        memset(vis,false,sizeof(vis));
        cin>>l;
        cin>>sx>>sy>>ex>>ey;
        vis[sx][sy]=true;
        bfs();
    }
}

http://ybt.ssoier.cn:8088/problem_show.php?pid=1257