用栈实现广度优先搜索(BFS)解决迷宫问题

# 定义一个节点类，该节点包含了单元的坐标和节点的父节点，用于记录路径。class Node: def __init__(self, row, col, parent=None): self.row = row self.col = col self.parent = parent# 实现一个函数，用于判断单元格是否为障碍物，以及将起点和终点添加到栈中。def is_valid(maze, row, col): if row < 0 or row >= len(maze) or col < 0 or col >= len(maze[0]) or maze[row][col] == 1: return False return Truedef solve_maze(maze, start, end): stack = [Node(start[0], start[1])] # 将起点加入栈中 visited = [[False for _ in range(len(maze[0]))] for _ in range(len(maze))] visited[start[0]][start[1]] = True while stack: cur_node = stack.pop() # 弹出栈顶元素 if cur_node.row == end[0] and cur_node.col == end[1]: # 如果到达终点，则返回路径 path = [] while cur_node: path.append((cur_node.row, cur_node.col)) cur_node = cur_node.parent return path[::-1] # 返回从起点到终点的路径 # 将当前节点的相邻未访问节点加入栈中 for row, col in [(cur_node.row, cur_node.col-1), (cur_node.row+1, cur_node.col), (cur_node.row, cur_node.col+1), (cur_node.row-1, cur_node.col)]: if is_valid(maze, row, col) and not visited[row][col]: next_node = Node(row, col, cur_node) stack.append(next_node) visited[row][col] = True return None # 如果没有路径，则返回 None# 定义一个迷宫进行测试：maze = [ [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)print(solve_maze(maze, start, end))# 输出：[(0, 0), (1, 0), (2, 0), (2, 1), (2, 2), (3, 2), (4, 2), (4, 3), (4, 4)]