洛谷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$。

P1443 马的遍历 - 洛谷

思路

题目说的很清晰，就是给定一个 $n\times{m}$ 大的棋盘，问一个在 $(x,y)$ 点处的马，到棋盘上每个点的最少步数

看到最少步数，就应该很自然的想到BFS，BFS的性质决定了搜索到的第一个正确答案花的步数就是最少步数，为此我们只需要遍历这张图，把步数标上去，最后打印图即可

样例图解

y\x	1	2	3
1	马	3	2
2	3	-1	1
3	2	1	4

bfs核心代码

struct pos {
  int x, y;
};
int n, m;
int dx[]{-2, -2, -1, -1, 2, 2, 1, 1}, 
    dy[]{-1, 1, -2, 2, -1, 1, -2, 2};
void bfs(int x, int y) {
  std::queue<pos> q;
  q.push({x, y});
  theMap[x][y] = 0;
  visited[x][y] = true;
  while (not q.empty()) {
    auto p = q.front();
    q.pop();
    for (int i = 0; i < 8; i++) {
      int px = p.x + dx[i], py = p.y + dy[i];
      if (px >= 1 and px <= n and py >= 1 and py <= m and 
            (not visited[px][py])) {
        theMap[px][py] = theMap[p.x][p.y] + 1;
        q.push({px, py});
        visited[px][py] = true;
      }
    }
  }
}

C with STL代码

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int main() {
    struct pos {
        int x, y;
    };
    int n, m, x, y,
            dx[]{-2, -2, -1, -1, 2, 2, 1, 1},
            dy[]{-1, 1, -2, 2, -1, 1, -2, 2};
    cin >> n >> m >> x >> y;
    vector<vector<int>> theMap(n + 1);
    vector<vector<bool>> visited(n + 1);
    for (int i = 1; i <= n; i++) {
        theMap[i].resize(m + 1);
        visited[i].resize(m + 1);
        fill(theMap[i].begin(), theMap[i].end(), -1);
        fill(visited[i].begin(), visited[i].end(), false);
    }
    queue<pos> q;
    q.push({x, y});
    theMap[x][y] = 0;
    visited[x][y] = true;
    while (not q.empty()) {
        auto p = q.front();
        q.pop();
        for (int i = 0; i < 8; i++) {
            int px = p.x + dx[i], py = p.y + dy[i];
            if (px >= 1 and px <= n and py >= 1 and py <= m and
                (not visited[px][py])) {
                theMap[px][py] = theMap[p.x][p.y] + 1;
                q.push({px, py});
                visited[px][py] = true;
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++)
            printf("%-5d", theMap[i][j]);
        putchar('\n');
    }
    return 0;
}

AC截图

BFS的情况比较复杂，不是很容易封装成一个模板函数，这里就不写CPP匿名函数的版本了