代码实现:位置[0,2]、[1,0]小区,位置[0,0]是垃圾站,位置[0,1]、[1,1]是障碍,无法通行,2个小区,1个垃圾站,小区到垃圾站的最小路径是1+0=1。
时间: 2024-09-12 17:02:17 浏览: 53
在您给出的例子中,这是一个二维数组表示的地图,我们需要找出两个小区[0,2]和[1,0]以及一个垃圾站[0,0]之间最短的路径。由于[0,1]和[1,1]位置不可通行,所以我们不能直接通过它们。在这种情况下,可以先将障碍位置设为无穷大(例如`np.inf`),这样它们就不会出现在搜索路径中。以下是使用Python和NumPy库(如果有需要的话)的一个简单实现:
```python
import numpy as np
# 定义地图数组
map_array = np.array([[0, 1, np.inf, np.inf],
[1, 0, np.inf, 2],
[np.inf, np.inf, 1, np.inf],
[np.inf, 2, np.inf, 0]])
# 垃圾站和小区的位置
garbage_station = (0, 0)
neighborhoods = [(0, 2), (1, 0)]
# 创建一个表示距离的数组,初始化为无穷大
distances = np.full_like(map_array, np.inf)
# 设置起点(垃圾站)的距离为0
distances[garbage_station] = 0
# 使用宽度优先搜索(BFS)
visited = np.zeros_like(distances, dtype=bool)
queue = [(garbage_station, 0)] # 用元组存储坐标和距离
while queue:
current_pos, distance = queue.pop(0)
if visited[current_pos]: # 如果已经访问过,则跳过
continue
visited[current_pos] = True
for neighbor in [(i, j) for i in range(-1, 2) for j in range(-1, 2) if abs(i) + abs(j) == 1]:
next_pos = (current_pos[0] + neighbor[0], current_pos[1] + neighbor[1])
if 0 <= next_pos[0] < map_array.shape[0] and 0 <= next_pos[1] < map_array.shape[1]:
if map_array[next_pos] != np.inf and not visited[next_pos]:
# 只有邻居是小区并且没有遇到障碍才更新距离
new_distance = distance + map_array[next_pos]
if new_distance < distances[next_pos]:
distances[next_pos] = new_distance
queue.append((next_pos, new_distance))
# 找出两个小区的最短距离
shortest_path = np.min([distances[i] + map_array[i] for i in neighborhoods]) if any(distances[neighborhoods]) else None
print("小区到垃圾站的最小路径长度:", shortest_path)
```
阅读全文