Python栈的应用：迷宫问题求解
迷宫问题可以使用深度优先搜索算法来解决，而栈可以作为深度优先搜索的数据结构进行实现。
具体的思路如下：
-
将起点入栈并标记为已访问；
-
当栈不为空时，取出栈顶元素作为当前位置，如果当前位置为终点，则输出路径并结束程序；
-
否则，按照上、右、下、左的顺序，判断当前位置周围能否行走，如果可以，则将其入栈并标记为已访问；
-
如果周围都不能行走，则退栈，回溯到上一个位置，继续进行步骤2。
具体的代码演示如下：
maze = [ [1, 1, 1, 1, 1], [0, 0, 1, 0, 0], [1, 1, 1, 0, 1], [1, 0, 0, 0, 1], [1, 1, 1, 1, 1] ] # 迷宫地图，1表示障碍物，0表示可行走的空间 stack = [(0, 0)] # 起点入栈 visited = [[False] * 5 for _ in range(5)] # 标记数组 def dfs(): while stack: x, y = stack[-1] # 取出栈顶元素 if (x, y) == (4, 4): # 到达终点，输出路径 for i, j in stack: print(f'({i}, {j})', end=' -> ') print('(4, 4)') return can_move = False # 标记周围是否有可行的位置 for dx, dy in [(-1, 0), (0, 1), (1, 0), (0, -1)]: # 上、右、下、左的顺序 nx, ny = x + dx, y + dy if 0 <= nx < 5 and 0 <= ny < 5 and not visited[nx][ny] and not maze[nx][ny]: stack.append((nx, ny)) visited[nx][ny] = True can_move = True break if not can_move: # 周围都不能行走，退栈 stack.pop() dfs() # 开始搜索
运行结果如下：
(0, 0) -> (1, 0) -> (2, 0) -> (2, 1) -> (2, 2) -> (1, 2) -> (1, 3) -> (0, 3) -> (0, 4) -> (1, 4) -> (2, 4) -> (3, 4) -> (4, 4)
相关文章