每日一题-20th

⭐每日一题⭐专栏

written by SJTU-XHW

本人学识有限，解析难免有错，恳请读者能够批评指正，本人将不胜感激！

LuoGu P1443. 马的遍历

题目描述

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

说明

输入格式

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

输出格式

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

样例 1 输入

3 3 1 1

样例 1 输出

1
2
3

0    3    2    
3    -1   1    
2    1    4

数据规模与约定

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

思路

毫无疑问，棋盘的每一个点都存在一个二维数组中最为方便；从起点 $(x,y)$ 出发（值为 0），允许：$(-1,+2),\space(+1,+2),\space(+2,+1),\space(+2,-1),\space(+1,-2),\space(-1,-2),\space(-2,-1),\space(-2,+1)$ 共 8 种移动方式。

由于是最短步数，所以必须使用 bfs 队列（借鉴图的最短路径思想），防止不等长影响最短路径的判断；

每移动一次到达的位置上的值为原来的值 + 1，如果原来被给定了值，就放弃这条路径；如果出界，则也放弃这条路径；

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;

int area[401][401];
int n, m;

struct point {
    int x;
    int y;
    bool isValid() const {
        return x > 0 && x <= n && y > 0 && y <= m && area[x][y] == -1;
    }
};
point steps[8] = {{-1,2},{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1},{-2,1}};
queue<point> tasks;

int main() {
    int x, y;
    scanf("%d%d%d%d", &n, &m, &x, &y); point cur = {x, y}, from; 
    memset(area, -1, sizeof(area)); area[x][y] = 0;
    tasks.push(cur);
    while (!tasks.empty()) {
        from = tasks.front(); tasks.pop();
        for (int i = 0; i < 8; ++i) {
            point to = {from.x + steps[i].x, from.y + steps[i].y};
            if (to.isValid()) {
                area[to.x][to.y] = area[from.x][from.y] + 1;
                tasks.push(to);
            }
        }
    }
    
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j)
            printf("%d\t", area[i][j]);
        printf("\n");
    }
    return 0;
}

一遍过。就这？普及/提高-？【狗头保命，溜了溜了】