简单的路径搜索代码
时间: 2023-08-06 20:17:05 浏览: 22
以下是一个简单的路径搜索代码示例,使用的是BFS算法:
```python
from collections import deque
# 定义地图和起点、终点坐标
map = [
[0, 1, 0, 0, 0],
[0, 1, 0, 1, 0],
[0, 0, 0, 0, 0],
[0, 1, 1, 1, 0],
[0, 0, 0, 1, 0]
]
start = (0, 0)
end = (4, 4)
# 定义四联通方向
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
# 定义BFS算法
def bfs(start, end, map):
queue = deque([(start, 0)])
visited = set([start])
while queue:
node, depth = queue.popleft()
if node == end:
return depth
for direction in directions:
neighbor = (node[0] + direction[0], node[1] + direction[1])
if neighbor[0] >= 0 and neighbor[0] < len(map) and neighbor[1] >= 0 and neighbor[1] < len(map[0]) and map[neighbor[0]][neighbor[1]] == 0 and neighbor not in visited:
queue.append((neighbor, depth + 1))
visited.add(neighbor)
return -1
# 调用BFS算法并输出结果
result = bfs(start, end, map)
print(result)
```
该代码使用了一个二维数组表示地图,0表示可以通过,1表示障碍物。定义了起点、终点坐标和四联通方向。使用BFS算法进行搜索,每次取出队列中的节点,判断是否为终点,如果不是则将其四联通的邻居加入队列中。为了避免重复搜索,使用了一个visited集合记录已经遍历过的节点。最后返回搜索的深度,即最短路径的长度。