P3706. 跳马问题

解题思路

单匹马的跳跃情况

假设已知某匹马的坐标和最大跳跃步数，则可以用 BFS 计算出该匹马能够到达地图上某个点的 最小步数。比如对于以下初始位于 (0, 0) 位置、最多能跳 4 步的马：

考虑它跳跃到地图上各个点所花费的步数：

跳跃 0 步

跳跃 1 步

跳跃 2 步

跳跃 3 步

跳跃 4 步

因此可以通过 BFS 过程得到这匹马可以到达的最终状态。其代码如下：

多匹马的跳跃情况

对于每一匹马，都可以计算出对应的二维矩阵 mat。考虑多匹马的情况，将所有马的 mat 叠加成一个总的二维矩阵 ans_mat，对于每一个点 (x, y) 而言，其逻辑如下：

• 若 ans_mat[x][y] 已经为 -1，说明有其他马无法到达点 (x, y)
• 若某匹马的 mat[x][y] 为 -1，说明这匹马无法到达点 (x, y)，将 ans_mat[x][y] 改为 -1
• 若 ans_mat[x][y] 和 mat[x][y] 均不为 -1，则将 mat[x][y] 叠加到 ans_mat[x][y] 中

考虑 2 匹马的简单例子，可以从以下例子看出上述逻辑。假设初始矩阵为：

那么位置为 (0, 0) 的马的最终可到达情况矩阵 mat 为：

位置为 (1, 2) 的马的最终可到达情况矩阵 mat 为：

其中 -1 用 . 来表示。两者的叠加结果为：

可以看出，所有马跳到同一个位置的最小的步数就为 1。

复杂度分析 设棋盘为 m 行 n 列，棋盘上共有 h 匹马（即数字格子的个数，h 最大可达 m*n）。对每一匹马调用一次 bfs4SingleHorse：该 BFS 中 mat 数组兼做检查数组，每个格子至多入队一次，每次出队检查 8 个「日」字方向，故单次 BFS 为 O(m*n)；随后把这匹马的 mat 叠加进 ans_mat 又是一次 O(m*n) 的双重遍历。因此主体部分为 O(h*m*n)，最坏情况下（几乎格格都是马）达到 O(m^2*n^2)，这是整个算法的瓶颈。最后扫一遍 ans_mat 取非 -1 位置的最小值是 O(m*n)，不影响量级。空间上，单匹马的 mat、叠加用的 ans_mat 以及 BFS 队列都是 O(m*n)，每匹马的 mat 用完即可回收，故空间复杂度为 O(m*n)。