给定一个大小为 n 行 m 列的棋盘,棋盘的左上角坐标为 (1, 1),右下角坐标为 (n, m)。在棋盘上的某个起始点 (x, y) 放置了一个中国象棋的马。马走“日”字,即可以横向移动两格纵向移动一格,或横向移动一格纵向移动两格。请你计算出马从起始点 (x, y) 出发,到达棋盘上任意一个点最少需要走几步。如果某个点无法到达,则输出 -1。
题目要求我们计算中国象棋的马从初始位置(x, y)到达棋盘上所有其他点的最少步数,即求解最短路径问题。
马走“日”字,即可以横向移动两格纵向移动一格,或横向移动一格纵向移动两格。棋盘的大小为n × m,其中1 ≤ n, m ≤ 400。
为了求解最短路径问题,特别是这种网格上的移动问题,广度优先搜索(BFS)是最合适的算法。
BFS能够确保第一次访问某个点时,所用的步数就是最短步数。
初始化:
创建一个n × m的矩阵dist,初始值设为-1,表示未访问。
将起始点(x, y)的dist值设为0,并加入队列。
BFS遍历:
从队列中取出当前点,检查其所有可能的8个移动方向。
对于每个移动方向,计算新位置(nx, ny),如果新位置在棋盘内且未被访问过,则更新dist[nx][ny]为当前步数加1,并将新位置加入队列。
输出结果:
遍历dist矩阵,输出每个点的最短步数。
输入只有一行,包含四个整数,分别为 n, m, x, y,表示棋盘的行数、列数以及马的起始坐标。
1 ≤ n, m ≤ 400
1 ≤ x ≤ n
1 ≤ y ≤ m
输出一个 n × m 的矩阵,矩阵中的每个元素表示马从起始点 (x, y) 到达该点的最少步数。如果无法到达,则对应位置输出 -1。
数字之间用一个空格分隔。