算法题：horse

问题描述

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

输入格式

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

输出格式

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

样例1

输入

5 8 2 2

输出

4 3 2 1 2 3 4 3
3 0 3 2 3 2 3 4
2 3 2 1 2 3 4 3
1 2 1 4 3 2 3 4
2 3 2 3 2 3 4 3

样例2

输入

4 5 3 2

输出

1 2 1 4 3
2 3 2 1 2
3 0 3 2 3
4 3 2 1 2

数据范围

1≤x≤n≤400,1≤y≤m≤400

解决方案

思路

广度优先搜索

代码

#include <iostream>
#include <queue>

using namespace std;

int main() {
    int n, m;
    int x, y;
    int dis[405][405];
    cin >> n >> m >> x >> y;

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            dis[i][j] = -1;
        }
    }
    dis[x][y] = 0;

    queue<pair<int, int>> q;
    q.push({x, y});

    int offset_x[] = {2, 2, 1, 1, -1, -1, -2, -2};
    int offset_y[] = {-1, 1, -2, 2, -2, 2, -1, 1};
    while (!q.empty()) {
        pair<int, int> point = q.front();
        q.pop();
        for (int i = 0; i < 8; ++i) {
            int xx = point.first + offset_x[i];
            int yy = point.second + offset_y[i];
            if (xx >= 1 && x <= n && yy >= 1 && yy <= m && dis[xx][yy] == -1) {
                dis[xx][yy] = dis[point.first][point.second] + 1;
                q.push({xx, yy});
            }
        }
    }

    for (int i = 1; i <= n; ++i) {
        if (i != 1)
            cout << endl;
        for (int j = 1; j <= m; ++j) {
            if (j != 1)
                cout << " ";
            cout << dis[i][j];
        }
    }
    return 0;
}