有一个n*m的棋盘(1<n,m<=400)，在某个点上有一个马,要求你计算出马到达棋盘上任意一个点最少要走几步

思路：

可以使用BFS来求解，将起点加入队列中，然后进行BFS搜索。搜索时，需要记录每个点到达的步数，并将已经搜索过的点标记为已访问。每次从队列中取出一个点，按照马的移动规则依次将可以到达的点加入队列中。如果目标点被搜索到，则返回其到起点的步数。

具体实现：

1. 定义一个结构体Point用来表示一个点的横坐标和纵坐标。

2. 编写一个函数valid(x, y)用来判断点(x, y)是否越界。

3. 编写一个BFS函数search(x0, y0, x, y)用来求解马从(x0, y0)到达(x, y)的最短距离。

4. 在函数中先初始化一个bool型的visit数组用来记录每个点是否被访问过，将起点加入队列，并设置visit[x0][y0]为true。

5. 使用一个while循环，取出队首的点，依次计算马可以到达的8个点，并判断其是否越界以及是否已经被访问过。

6. 如果到达了目标点(x, y)，则返回其到起点的步数。

代码实现：

相关问题

有一个n*m的棋盘(1<n,m<=400)，在某个点上有一个马,要求你马从起点分别到达所有点的最少步数之和

这个问题可以使用广度优先搜索（BFS）解决。

我们可以把每个格子看作一个节点，马能够到达的格子之间连一条边，边权为1。然后我们从起点开始，对整个图进行BFS搜索，求出每个节点到起点的最短距离。由于马只能向8个方向走，我们可以使用一个数组来表示8个方向的偏移量。

以下是代码实现：

from collections import deque

def bfs(n, m, start):
    dist = [[-1] * m for _ in range(n)]  # 初始化距离为-1，表示尚未访问
    dist[start[0]][start[1]] = 0  # 起点距离为0
    q = deque([start])  # 使用队列保存待访问的节点

    dx = [-2, -2, -1, -1, 1, 1, 2, 2]  # 8个方向的偏移量
    dy = [-1, 1, -2, 2, -2, 2, -1, 1]

    while q:
        x, y = q.popleft()
        for i in range(8):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < n and 0 <= ny < m and dist[nx][ny] == -1:
                dist[nx][ny] = dist[x][y] + 1
                q.append((nx, ny))

    return dist

n, m = 4, 4  # 棋盘大小
start = (0, 0)  # 起点位置
dist = bfs(n, m, start)
ans = sum(sum(dist[i][j] for j in range(m)) for i in range(n))  # 所有节点到起点的最短距离之和
print(ans)

时间复杂度为O(nm)，空间复杂度也为O(nm)。

题目描述 有一个n*m的棋盘(1<n,m<=400)，在某个点上有一个马,要求你计算出马到达棋盘上任意一个点最少要走几步 输入 一行四个数据，棋盘的大小和马的坐标 输出 一个n*m的矩阵，同一行元素之间用空格分离。代表马到达某个点最少要走几步。不能到达则输出-1。

解题思路：

本题属于搜索算法，使用 BFS（广度优先搜索）进行求解。以马所在的位置为起点，不断进行广度扩展，直到扩展到目标位置，或者无法继续扩展为止。

- 首先判断目标点是否在棋盘内，如果不在，直接输出-1；
- 定义一个距离数组，记录每个位置到起点的距离；
- 定义一个队列，初始化为起点，并将距离数组对应位置赋值为 0；
- 利用队列进行广度优先搜索，每次取出队头位置，根据移动规则，将可以到达的位置加入队列；
- 如果目标点已经被搜索到，直接输出距离数组对应位置的值；
- 如果队列已经为空，说明无法到达目标点，输出-1。

算法流程：

- 判断目标点是否在棋盘内，如果不在，直接输出-1；
- 定义距离数组，初始化为-1；
- 将起点加入队列，距离值初始化为0，并将距离数组对应位置设为0；
- 对于队列中的每个位置，判断是否为目标点，如果是，直接返回距离数组对应值；
- 如果不是目标点，根据移动规则，将可以走到的位置加入队列，距离值更新为当前距离值加一，并将距离数组对应位置更新；
- 如果队列为空，说明无法到达目标点，直接输出-1.

C++ 代码：