Python 栈与 DFS 算法破解 m×n 迷宫路径问题

要解决这个迷宫问题，我们可以使用深度优先搜索（DFS）算法，并利用栈来保存访问路径。以下是对应的 Python 实现： ```python class Stack: def __init__(self): self.items = [] def push(self, item): self.items.append(item) def pop(self): return self.items.pop() def is_empty(self): return len(self.items) == 0 def peek(self): return self.items[-1] def maze_solver(maze, start, end): rows = len(maze) cols = len(maze[0]) stack = Stack() stack.push(start) visited = set() # 定义四个方向上下左右 directions = [(1, 0), (0, 1), (-1, 0), (0, -1)] while not stack.is_empty(): current = stack.pop() # 如果到达终点，返回路径 if current == end: return visited.union({current}) # 标记当前节点为已访问 visited.add(current) # 检查四个方向 for direction in directions: next_row = current[0] + direction[0] next_col = current[1] + direction[1] next_cell = (next_row, next_col) # 检查边界和可通行性 if (0 <= next_row < rows and 0 <= next_col < cols and maze[next_row][next_col] == 0 and next_cell not in visited): stack.push(next_cell) return [] # 如果没有找到路径 def print_path(path): for point in path: print(point[0] + 1, point[1] + 1) # 输出时转换为1-indexed def main(): # 读取输入 m, n = map(int, input().split()) maze = [list(map(int, input().split())) for _ in range(m)] start = (1, 1) # 起点 end = (m-2, n-2) # 终点 path = maze_solver(maze, start, end) if path: print_path(path) else: print("没有路径") if __name__ == "__main__": main() ``` 代码说明： 1. Stack类：用来实现栈的基本操作，包括 push、pop、peek 和检查是否为空。 2. maze_solver函数：实现深度优先搜索，查找从起点到终点的路径。 - 使用一个栈来模拟系统的调用栈。 - 采用四个方向（下、右、上、左）进行探测。 - 如果到达终点，返回当前路径。 - 如果当前节点有效且未被访问，则将其压入栈中。 3. print_path函数：格式化输出路径，坐标加1以满足1-index。 4. main函数：处理输入输出，初始化迷宫，并调用路径求解函数。 输入输出： 输入格式： ``` 5 6 1 1 1 1 1 1 1 0 0 1 0 1 1 1 0 1 0 1 1 0 0 0 0 1 1 1 1 1 1 1 ``` 输出格式： ``` 1 1 1 2 2 2 3 2 3 3 3 4 ``` 你可以在本地环境中运行这个 Python 代码来处理不同的迷宫问题。确保提供的输入格式与示例相符。 ######[AI写代码神器 | 1682点数解答 | 2024-11-03 12:34:06]