写一个用栈算迷宫问题的python
时间: 2023-08-04 14:14:20 浏览: 38
以下是用栈算迷宫问题的 Python 代码:
```python
def solve_maze(maze):
stack = []
visited = set()
start = (0, 0)
stack.append(start)
while stack:
x, y = stack[-1]
if (x, y) == (len(maze)-1, len(maze[0])-1):
return stack
if (x, y) not in visited:
visited.add((x, y))
neighbors = get_neighbors(x, y, maze)
for n in neighbors:
stack.append(n)
break
else:
stack.pop()
return None
def get_neighbors(x, y, maze):
neighbors = []
if x > 0 and maze[x-1][y] == 0:
neighbors.append((x-1, y))
if y > 0 and maze[x][y-1] == 0:
neighbors.append((x, y-1))
if x < len(maze)-1 and maze[x+1][y] == 0:
neighbors.append((x+1, y))
if y < len(maze[0])-1 and maze[x][y+1] == 0:
neighbors.append((x, y+1))
return neighbors
# Example usage
maze = [[0, 1, 1, 1],
[0, 0, 0, 1],
[1, 1, 0, 0],
[1, 1, 1, 0]]
solution = solve_maze(maze)
if solution:
print(solution)
else:
print("No solution found")
```
这个算法使用了一个栈来记录当前已经访问过的位置,以及一个集合来记录已经访问过的位置,避免重复访问。在每个迭代中,算法会检查当前位置是否是终点,如果是,返回栈。否则,算法会获取当前位置的所有邻居,如果邻居中存在未访问过的位置,将其入栈并停止循环。如果所有邻居都已经访问过,将当前位置出栈。如果栈为空,说明没有找到解决方案。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)