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++实现
时间: 2024-03-07 15:53:23 浏览: 12
这是一道经典的搜索问题,可以使用广度优先搜索(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)):
```python
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的矩阵,表示整张地图。最后返回的是起点到终点的最短距离。
stm32f103cxt6
STM32F103CXT6是一款32位的ARM Cortex-M3微控制器,由意法半导体(STMicroelectronics)生产。它具有高性能、低功耗和丰富的外设接口,适用于各种应用领域,如工业控制、汽车电子、医疗设备等。这款微控制器采用了高密度CMOS工艺,集成了闪存、SRAM和多种外设。它支持多种通信接口,如SPI、I2C和USART,并具有多个定时器和ADC通道,可以满足各种应用的需求。