备战蓝桥杯Day16 - 栈应用(迷宫问题)

 迷宫问题

 基本介绍：

使用栈来实现迷宫问题，用数字1表示墙，不可通过，用数字0表示路，可以通过。

基本步骤

1. 初始化：创建一个栈，并将起点坐标压入栈中。同时，你可能需要一个与迷宫大小相同的二维数组来跟踪访问过的单元格，以及一个表示迷宫本身的二维数组。
2. 开始搜索：当栈不为空时，从栈顶弹出一个单元格，并检查它是否是终点。如果是，则你已经找到了路径，可以结束搜索。
3. 探索相邻单元格：如果弹出的单元格不是终点，则检查其所有相邻的单元格（通常是上、下、左、右四个方向）。对于每个未访问过的相邻单元格，如果它是一个有效的迷宫单元格（即在迷宫边界内且不是障碍物），则将其标记为已访问，并将其坐标压入栈中。
4. 重复搜索：重复步骤2和3，直到找到终点或栈为空（表示没有路径）。
5. 处理结果：如果找到终点，则可以通过从终点回溯到起点的方式来提取路径。这通常涉及到另一个栈或递归调用。如果没有找到路径，则输出相应的消息。

 代码实现

maze = [
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    [1, 0, 0, 1, 0, 0, 0, 1, 0, 1],
    [1, 0, 0, 1, 0, 0, 0, 1, 0, 1],
    [1, 0, 0, 0, 0, 1, 1, 0, 0, 1],
    [1, 0, 1, 1, 1, 0, 0, 0, 0, 1],
    [1, 0, 0, 0, 1, 0, 0, 1, 0, 1],
    [1, 0, 1, 0, 0, 0, 1, 0, 0, 1],
    [1, 0, 0, 1, 1, 0, 1, 1, 0, 1],
    [1, 1, 0, 0, 0, 0, 1, 0, 0, 1],
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
]

dirs = [  # 将上下左右四个方向封装在匿名函数中
    lambda x, y:(x-1, y),  # 上
    lambda x, y:(x+1, y),  # 下
    lambda x, y:(x, y-1),  # 左
    lambda x, y:(x, y+1),  # 右

]

def maze_path(x1, y1, x2, y2):
    stack = []
    stack.append((x1, y1))
    while (len(stack)>0):
        curNode = stack[-1]     # 当前的节点
        if curNode[0]== x2 and curNode[1] == y2:
            # 走到终点了
            for p in stack:
                print(p)
            return True
        for dir in dirs:
            nextNode = dir(curNode[0], curNode[1])
            # 如果下一个节点能走
            if maze[nextNode[0]][nextNode[1]] == 0:
                stack.append(nextNode)
                maze[nextNode[0]][nextNode[1]] = 2  # 2表示已经走过
                break
        else:
            maze[nextNode[0]][nextNode[1]] = 2
            stack.pop()
    else:
        print("没有路")
        return False

maze_path(1,1,8,8)

学习总结

哈哈哈终于开学了，这学期十几门课。这跟高三生有什么区别啊哈哈哈哈，每天都会在b溃的边缘，还有很多虚假的社交和不停的内卷，这谁能受得了啊哈哈哈哈，虽然我卷不过他们，但是咱也不能让人卷的太多了，多少还是学点吧。明天早八上到晚八，哈哈哈真受不了。祝大家开学快乐吧（我不快乐），新学期新气象，使劲学酷酷学猛猛学，干就完事了！！！