马的遍历

题目描述

有一个n×m 的棋盘，在某个点 (x, y) 上有一个马，要求你计算出马到达棋盘上任意一个点最少要走几步。

输入

输入只有一行四个整数，分别为 n, m, x, y。

输出

一个n×m 的矩阵，代表马到达某个点最少要走几步（不能到达则输出−1）。

样例输入

3 3 1 1

样例输出

0    3    2    
3    -1   1    
2    1    4

提示

bfs板子题 

#include<bits/stdc++.h>

using namespace std;

queue <int> x;
queue <int> y;
queue <int> s;

int dx[9]={0,-1,-2,-2,-1,1,2,2,1};
int dy[9]={0,-2,-1,1,2,2,1,-1,-2};
int mp[500][500],vis[500][500],m,n,sx,sy;

int main()
{
    cin>>m>>n>>sx>>sy;
    
    x.push(sx);//记录x坐标
    y.push(sy);//记录y坐标
    s.push(0);//记录所用步数
    
    while(!x.empty())
    {
        int tx=x.front();
        int ty=y.front();
        int ts=s.front();
        x.pop();
        y.pop();
        s.pop();
        for(int i=1;i<=8;++i)
        {
            int xx=tx+dx[i];
            int yy=ty+dy[i];
            if(xx>0&&yy>0&&xx<=m&&yy<=n&&vis[xx][yy]==0&&mp[xx][yy]==0)
　　　　　　　//对⑧个方向遍历 如果第一次到达就记录下步数
            {
                x.push(xx);
                y.push(yy);
                s.push(ts+1);
　　　　　　　　　//储存新标记的的点
                vis[xx][yy]=1;
                mp[xx][yy]=ts+1;
            }
        }
    }
    
    mp[sx][sy]=0;
    
    for(int i=1;i<=m;++i)
    {
        for(int j=1;j<=n;++j)
        {
            if(vis[i][j]==1)
            {
                printf("%-5d",mp[i][j]);
　　　　　　　　　　//注意输出格式
            }
            else
            {
                printf("%-5d",-1);
            }
        }
        cout<<endl; 
    }
    
    return 0;
}