本文共 1941 字，大约阅读时间需要 6 分钟。

用栈解决迷宫问题

1. 问题

迷宫问题:

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, 0, 0, 1],[1, 0, 1, 0, 0, 0, 1, 0, 0, 1],[1, 0, 1, 1, 1, 0, 1, 1, 0, 1], [1, 1, 0, 0, 0, 0, 0, 0, 0, 1],[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]]

2. 解决思路

栈——深度优先搜索(回溯法)

3. 代码

'''TOPIC: 用栈解决迷宫问题author: Bluetime: 2020-08-12QQ: 2458682080'''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, 0, 0, 1],[1, 0, 1, 0, 0, 0, 1, 0, 0, 1],[1, 0, 1, 1, 1, 0, 1, 1, 0, 1], [1, 1, 0, 0, 0, 0, 0, 0, 0, 1],[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]]dirs = [    lambda x,y: (x - 1, y),   # 上    lambda x,y: (x, y + 1),   # 右    lambda x,y: (x + 1, y),   # 下    lambda x,y: (x, y - 1)    # 左 ]def maze_path(x1, y1, x2, y2):    stack = []    stack.append((x1, y1))    while(len(stack) > 0):   # 栈空表示没有路        current_node = stack[-1]  # 当前节点        # 判断当前是否走到了终点        if current_node[0] == x2 and current_node[1] == y2:            # 把路径打印出来            for p in stack:                print(p)            return True        # x, y四个方向: x, y-1; x+1, y; x, y+1; x-1, y        for dir in dirs:            next_node = dir(current_node[0], current_node[1])            # 如果下一个节点能走            if maze[next_node[0]][next_node[1]] == 0:                stack.append(next_node)                maze[next_node[0]][next_node[1]] = 2  # 表示已经走过                break        else:  # 如果4个位置都不能走了，该点就出栈            maze[current_node[0]][current_node[1]] = 2            stack.pop()    else:        print("无路可走，走投无路")        return Falsemaze_path(1, 1, 8, 8)

结果:

(1, 1)(2, 1)(3, 1)(4, 1)(5, 1)(5, 2)(5, 3)(6, 3)(6, 4)(6, 5)(7, 5)(8, 5)(8, 6)(8, 7)(8, 8)

路线为:

转载地址：http://jbiwi.baihongyu.com/