利用栈实现一条迷宫路径求解,利用队列实现迷宫最短路径求解,利用递归实现迷宫所有路径求解。
时间: 2024-06-11 11:09:58 浏览: 118
1. 利用栈实现迷宫路径求解:
算法步骤:
1. 将起点压入栈中,并将起点设置为已访问。
2. 对于栈顶元素,依次遍历其四个方向的相邻点,如果该点未访问且可以通过,则将该点压入栈中,并将其设置为已访问。
3. 如果栈顶元素为终点,则返回路径。
4. 如果栈顶元素无法继续移动,则弹出栈顶元素。
代码实现:
```python
def maze_path(maze, start, end):
stack = [start]
visited = set()
while stack:
curr = stack[-1]
if curr == end:
return stack
found = False
for next in [(curr[0]-1, curr[1]), (curr[0]+1, curr[1]), (curr[0], curr[1]-1), (curr[0], curr[1]+1)]:
if next not in visited and maze[next[0]][next[1]] == 0:
stack.append(next)
visited.add(next)
found = True
break
if not found:
stack.pop()
return None
```
2. 利用队列实现迷宫最短路径求解:
算法步骤:
1. 将起点加入队列,并将其设置为已访问。
2. 当队列不为空时,取出队首元素,遍历其四个方向的相邻点,如果该点未访问且可以通过,则将该点加入队列,并将其设置为已访问。
3. 如果该点为终点,则返回路径长度。
4. 如果队列为空,则表示无法到达终点。
代码实现:
```python
def maze_shortest_path(maze, start, end):
queue = [(start, 1)]
visited = set()
visited.add(start)
while queue:
curr, step = queue.pop(0)
if curr == end:
return step
for next in [(curr[0]-1, curr[1]), (curr[0]+1, curr[1]), (curr[0], curr[1]-1), (curr[0], curr[1]+1)]:
if next not in visited and maze[next[0]][next[1]] == 0:
queue.append((next, step+1))
visited.add(next)
return -1
```
3. 利用递归实现迷宫所有路径求解:
算法步骤:
1. 从起点开始,依次遍历其四个方向的相邻点,如果该点未访问且可以通过,则将其加入路径中,并将其设置为已访问。
2. 如果该点为终点,则将当前路径加入结果集中。
3. 如果该点无法继续移动,则将其从路径中删除。
4. 对于路径中的每一个点,重复步骤1-3。
代码实现:
```python
def maze_all_paths(maze, start, end, path, paths):
path.append(start)
if start == end:
paths.append(path[:])
else:
for next in [(start[0]-1, start[1]), (start[0]+1, start[1]), (start[0], start[1]-1), (start[0], start[1]+1)]:
if next not in path and maze[next[0]][next[1]] == 0:
maze_all_paths(maze, next, end, path, paths)
path.pop()
```
阅读全文