p1443

本题要求计算国际象棋中马从起点 出发到达棋盘上任意一点的最少步数。马的移动规则为“日”字形（8个可能方向）。若某点不可达，则输出 。

方法思路

1. 问题分析：马在棋盘上的移动具有跳跃性，且每次移动有8种可能方向。需要计算从起点到所有点的最短路径，适合使用广度优先搜索（BFS），因为BFS天然适合求解无权图的最短路径。
2. 关键点：
   • 坐标转换：输入坐标通常为1-indexed（如 表示左上角），程序内部需转换为0-indexed处理。
   • BFS初始化：起点步数为0，其余点初始化为（表示不可达）。
   • 方向处理：马有8个移动方向，用两个数组 dx 和 dy 存储偏移量。
   • 边界检查：移动后需检查新坐标是否在棋盘范围内。
3. 算法选择：BFS按层遍历，首次访问某点时即是最短路径，时间复杂度 ，空间复杂度 ，在合理棋盘尺寸下高效可行。

代码示例

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main() {
    int n, m, x, y;
    cin >> n >> m >> x >> y;
    x--; y--; // 转换为0-indexed

    vector<vector<int>> dist(n, vector<int>(m, -1));
    int dx[8] = {2, 1, -1, -2, -2, -1, 1, 2};
    int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};

    queue<pair<int, int>> q;
    dist[x][y] = 0;
    q.push(make_pair(x, y));

    while (!q.empty()) {
        int curx = q.front().first;
        int cury = q.front().second;
        q.pop();
        for (int i = 0; i < 8; i++) {
            int nx = curx + dx[i];
            int ny = cury + dy[i];
            if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
                if (dist[nx][ny] == -1) {
                    dist[nx][ny] = dist[curx][cury] + 1;
                    q.push(make_pair(nx, ny));
                }
            }
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cout << dist[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}

BFS遍历：

• 起点入队，距离设为0。
• 循环处理队列：取出队首点，尝试8个方向移动。
• 若新位置在棋盘内且未访问（dist[nx][ny] == -1），更新距离并入队。

复杂度分析

时间复杂度：O(n × m)

• BFS遍历：算***对棋盘上每个可达的格子进行一次访问。在最坏情况下（所有格子都可达），需要处理所有 个格子。
• 每个格子的处理：对每个格子，尝试马的 8 个移动方向（常数时间操作）。
• 总操作次数：（常数系数在复杂度分析中忽略）。
• 辅助操作：
  • 初始化距离矩阵：
  • 输出结果矩阵：
• 总时间复杂度：

空间复杂度：O(n × m)

• 距离矩阵：存储 个整数的二维数组 dist，空间 。
• BFS队列：
  • 最坏情况下（如棋盘全连通），队列可能同时存储 个格子坐标。
  • 每个坐标存储为 pair<int, int>，空间 每个，总空间 。
• 方向数组：固定大小的 dx[8] 和 dy[8]，空间 。
• 总空间复杂度：