//众神云集、群魔乱舞、以一抵百、砥砺前行//P1443 马的遍历

女爷i 2023-02-13 11:54 40阅读 0赞

## 题目描述 ##

题目描述  
有一个n\*m的棋盘(1<n,m<=400)，在某个点上有一个马,要求你计算出马到达棋盘上任意一个点最少要走几步

输入格式  
一行四个数据，棋盘的大小和马的坐标

输出格式  
一个n\*m的矩阵，代表马到达某个点最少要走几步（左对齐，宽5格，不能到达则输出-1）

输入输出样例  
输入 \#1 复制  
3 3 1 1  
输出 \#1 复制  
0 3 2  
3 -1 1  
2 1 4

## 题解 ##

BFS扫一遍，这题唯一要注意的点是输出格式，%-5d，不要妄想在数字后面加几个空格能解决格式问题。  
这题的马运动的方向，看我的dx和dy就好了（会象棋的一定懂）。

代码如下：

//------------------------------B F S--------------------------------//
    //*            //-------众神云集、群魔乱舞、以一抵百、砥砺前行---------//       *//
    //----------------------------Acmer LEO 到此一游------------------------------//
    #include<algorithm>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<vector>
    #include<queue>
    #include<stack>
    using namespace std;
    #define ll long long
    #define maxn 0x3f3f3f3f
    int map1[405][405];
    bool vis[405][405];
    int dx[8]= {
        1,2,2,1,-1,-2,-1,-2};
    int dy[8]= {
        2,1,-1,-2,2,1,-2,-1};
    int n,m;
    queue<int>bx;
    queue<int>by;
    void BFS()
    {
        
        int cur=0;
        while(!bx.empty())
        {
        
            int x=bx.front(),y=by.front();
            bx.pop();
            by.pop();
            for(int i=0; i<8; i++)
            {
        
                int xx=dx[i]+x;
                int yy=dy[i]+y;
                if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&!vis[xx][yy])
                {
        
                    vis[xx][yy]=1;
                    bx.push(xx);
                    by.push(yy);
                    map1[xx][yy]=map1[x][y]+1;
                }
            }
        }
    }
    int main()
    {
        
        memset(map1,maxn,sizeof(map1));
        int x,y;
        cin>>n>>m>>x>>y;
        map1[x][y]=0;
        bx.push(x);
        by.push(y);
        vis[x][y]=1;
        BFS();
        for(int i=1; i<=n; i++)
        {
        
            for(int j=1; j<=m; j++)
            {
        
                if(map1[i][j]!=maxn)
                printf("%-5d",map1[i][j]);
                else
                    printf("%-5d",map1[i][j]-maxn-1);
            }
            printf("\n");
        }
        return 0;
    }