地图是一个矩形，可以划分成M×N个方格。一些格子是岩石，还有一些沼泽，其余的只是美丽、纯净、湛蓝的水，因为Cxt不会游泳= =。Cxt每次站在一块岩石上想跳到另一块岩石上，他只能从一块岩石跳到另一块岩石上，既不能跳到水里也不能跳到沼泽里。因为Cxt有惊人的弹跳能力，他的跳法很像象棋中的马步:每次跳跃可以横移M1格，纵移M2格，或纵移M1格，横移M2格，最多有八个方向可供移动选择。请计算cx到达终点的最小步数输入数据保证终点是一定可达的. Input Format 第一行四个用空格分开的整数：M，N，M1和M2，1≤M，N≤30，1≤M1≤30，1≤M2≤30，M1≠M2 第二行到M+1行:第i+1行有N个用空格分开的整数描述了池塘第行的状态0为水，1为岩石，2为沼泽，3为起点4为终点。 Output Format第一行：从起点到终点的最少步数 Sample Input 4 5 1 2 1 0 1 0 1 3 0 2 0 4 0 1 2 0 0 0 0 0 1 0 Sample Output 2 数据说明 先跳到1行3列的岩石上，再跳到终点需要2步 时空磁盘限制（运行时） 时间限制：2000ms C++实现

这是一道经典的搜索问题，可以使用广度优先搜索（BFS）来解决。

具体做法如下：
1. 首先遍历整个地图，找到起点和终点的位置，可以使用一个二维数组来表示地图，0表示水，1表示岩石，2表示沼泽，3表示起点，4表示终点。
2. 使用一个队列来存储搜索中的状态，每个状态包括当前位置和当前步数。
3. 从起点开始，将起点的位置和步数入队。
4. 循环执行以下步骤，直到队列为空：
- 从队列中取出一个状态。
- 判断当前位置是否为终点，如果是，则返回当前步数，即为最短路径长度。
- 枚举当前位置可以跳到的所有位置，如果该位置是岩石或沼泽，且未被访问过，则将该位置和当前步数加一的状态入队。
5. 如果循环完毕后仍未找到终点，则说明终点不可达，返回-1表示无解。

需要注意的是，在判断当前位置是否为终点时，可以使用一个visited数组来标记已经访问过的位置，避免重复访问。

代码如下：

相关问题

Cxt出发了，他要去找时光机，可是距离好远，因为他生存在远古时期，木有轮船，飞机，大炮什么的。于是只能回去= =。地图是一个矩形，可以划分成M×N个方格。一些格子是岩石，还有一些沼泽，其余的只是美丽、纯净、湛蓝的水，因为Cxt不会游泳= =。Cxt每次站在一块岩石上想跳到另一块岩石上，他只能从一块岩石跳到另一块岩石上，既不能跳到水里也不能跳到沼泽里。因为Cxt有惊人的弹跳能力，他的跳法很像象棋中的马步:每次跳跃可以横移M1格，纵移M2格，或纵移M1格，横移M2格，最多有八个方向可供移动选择。请计算cx到达

时光机的最少跳跃次数。

这是一个经典的最短路径问题，可以使用广度优先搜索算法（BFS）来解决。具体步骤如下：

1. 将起点入队，距离初始化为0。

2. 在队列不为空的情况下，进行以下循环：

a. 将队列头部元素出队，判断是否为终点，如果是，返回距离；

b. 遍历八个方向，如果下一个点是合法的（不是水或沼泽），并且未被访问过，就将其入队，并标记为已访问。

3. 如果搜索完所有可能的路径都没有找到终点，返回-1。

代码实现如下（假设起点为(start_x, start_y)，终点为(end_x, end_y)）：

dx = [1, 1, 2, 2, -1, -1, -2, -2]
dy = [2, -2, 1, -1, 2, -2, 1, -1]

def bfs(start_x, start_y, end_x, end_y, grid):
    m, n = len(grid), len(grid[0])
    queue = [(start_x, start_y, 0)]
    visited = set([(start_x, start_y)])
    
    while queue:
        x, y, steps = queue.pop(0)
        if x == end_x and y == end_y:
            return steps
        for i in range(8):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] != 'W' and grid[nx][ny] != 'M' and (nx, ny) not in visited:
                queue.append((nx, ny, steps+1))
                visited.add((nx, ny))
    
    return -1

其中dx和dy分别表示横向和纵向的跳跃距离（M1和M2），visited用来记录访问过的点，grid是一个M*N的矩阵，表示整张地图。最后返回的是起点到终点的最短距离。

Cxt出发了，他要去找时光机，可是距离好远，因为他生存在远古时期，木有轮船，飞机，大炮什么的。于是只能回去= =。地图是一个矩形，可以划分成M×N个方格。一些格子是岩石，还有一些沼泽，其余的只是美丽、纯净、湛蓝的水，因为Cxt不会游泳= =。Cxt每次站在一块岩石上想跳到另一块岩石上，他只能从一块岩石跳到另一块岩石上，既不能跳到水里也不能跳到沼泽里。因为Cxt有惊人的弹跳能力，他的跳法很像象棋中的马步:每次跳跃可以横移M1格，纵移M2格，或纵移M1格，横移M2格，最多有八个方向可供移动选择。请计算cx到达终点的最小步数输入数据保证终点是一定可达的. Input Format 第一行四个用空格分开的整数：M，N，M1和M2，1≤M，N≤30，1≤M1≤30，1≤M2≤30，M1≠M2 第二行到M+1行:第i+1行有N个用空格分开的整数描述了池塘第行的状态0为水，1为岩石，2为沼泽，3为起点4为终点。 Output Format第一行：从起点到终点的最少步数 Sample Input 4 5 1 2 1 0 1 0 1 3 0 2 0 4 0 1 2 0 0 0 0 0 1 0 Sample Output 2 数据说明 先跳到1行3列的岩石上，再跳到终点需要2步 时空磁盘限制（运行时） 时间限制：2000ms C++实现

这是一道经典的搜索问题，可以使用广度优先搜索（BFS）来解决。

具体做法如下：
1. 首先遍历整个地图，找到起点和终点的位置，可以使用一个二维数组来表示地图，0表示水，1表示岩石，2表示沼泽，3表示起点，4表示终点。
2. 使用一个队列来存储搜索中的状态，每个状态包括当前位置和当前步数。
3. 从起点开始，将起点的位置和步数入队。
4. 循环执行以下步骤，直到队列为空：
- 从队列中取出一个状态。
- 判断当前位置是否为终点，如果是，则返回当前步数，即为最短路径长度。
- 枚举当前位置可以跳到的所有位置，如果该位置是岩石或沼泽，且未被访问过，则将该位置和当前步数加一的状态入队。
5. 如果循环完毕后仍未找到终点，则说明终点不可达，返回-1表示无解。

需要注意的是，在判断当前位置是否为终点时，可以使用一个visited数组来标记已经访问过的位置，避免重复访问。

代码如下：