传送锚点：https://www.luogu.com.cn/problem/P1443

题目描述

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

输入格式

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

输出格式

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

样例 #1

样例输入 #1

3 3 1 1

样例输出 #1

0    3    2    
3    -1   1    
2    1    4

提示

数据规模与约定

对于全部的测试点，保证 $1 \leq x \leq n \leq 400$，$1 \leq y \leq m \leq 400$。

思路

code

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
int n,m,x1,y1;
const int maxn = 410;
int dist[maxn][maxn];
int dx[8] = { -1,-2,-2,-1,1,2,2,1 };
int dy[8] = { -2,-1,1,2,2,1,-1,-2 };
typedef pair<int, int> PII;
queue<PII> q;
void bfs(int x,int y) {//x、y为当前遍历点坐标
    q.push({ x,y });
    while (q.size()) {
        auto t = q.front();
        q.pop();
        for (int i = 0; i < 8; i++) {
            int nx = t.first + dx[i];
            int ny = t.second + dy[i];
            if (nx<1 || nx>n || ny<1 || ny>m) continue;
            if (dist[nx][ny] != -1) continue;
            q.push({ nx,ny });
            dist[nx][ny] = dist[t.first][t.second] + 1;
        }
    }
}
int main()
{
    cin >> n >> m >> x1 >> y1;
    memset(dist, -1, sizeof(dist));
    dist[x1][y1] = 0;//1起始坐标标记为0
    bfs(x1, y1);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            printf("%-5d", dist[i][j]);
        }
        cout << endl;
    }
    return 0;
}