前言

hjs叫我看看这个走迷宫的程序，看了之后我感觉蛮有意思，就稍微改了一下，让它更直观一点

顺便添加一些注释

开始

出自网络

搜了一下这个程序出自网络，不知道是谁原创的了，
找到一篇比较详细，就当出处在这里（https://www.cnblogs.com/huchong/p/8522453.html）了

是python3的一个程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#迷宫
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-1, y), #上
    lambda x, y: (x, y-1), #左
    lambda x, y: (x, y+1)  #右
]

def solve_maze(x1,y1,x2,y2):
    # 空栈，用来存储正确的道路
    stack = []
    # 把初始位置放入，开始行走
    stack.append((x1,y1))
    maze[x1][y1] = 2  # 2表示已经走过的路
    # 通过判断栈的长度来决定是否进行尝试
    while len(stack) > 0:
        # 取出栈顶
        cur_node = stack[-1]
        if cur_node == (x2,y2): #如果到终点了，输出栈的内容，返回True
            print(stack)
            return True
        # 遍历 移动 列表， 找到合适的移动，同时将已经走过的路添加到栈内，标注为 2 
        for i in dirs:
            next_node = i(*cur_node)
            # 看看当前节点的上下左右操作之后，那个方向可以前进。
            if maze[next_node[0]][next_node[1]] == 0:
                stack.append(next_node)
                maze[next_node[0]][next_node[1]] = 2
                break
        # 如果是死胡同，就去栈顶，重新选择道路。
        else:
            stack.pop()
    else:
        # 如果栈空了，就打印没有结果，返回false
        print("没有结果")
        return False

solve_maze(1,1,8,8)

运行之后

我的

我稍微改动了一下，添加了一些注释

依然是python3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
'''
Edit by lx
Blog: blog.lxscloud.top
'''
import copy

#地图
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]
]
#走迷宫会改变地图，先拷贝一份原地图备用
maze_cp1 = []
maze_cp1 = copy.deepcopy(maze)#似乎只能进行深复制才有效

'''
功能：构造函数，可以根据需要将输入坐标处理为上，右，下，左
'''
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),  #左
]
id_d = ["向上走", "往右走", "向下走", "往左走"]

'''
功能：走迷宫
'''
def solve_maze(x1, y1, x2, y2, maze_cp):
    global stack_cp
    direction = []#创建一个记录“行走”的列表
    stack = []
    stack.append((x1,y1))#在路线里添加起始点
    direction.append("在原点")
    maze_cp[x1][y1] = 2
    while len(stack) > 0:   # 当栈不空循环
        cur_node = stack[-1]
        if cur_node == (x2,y2): #到达终点
            stack_cp = copy.deepcopy(stack)
            for ii, p in enumerate(stack):
                print(p, direction[ii])#将路线点和走法输出
            return True#结束，后面语句不运行
        for index_d, dir in enumerate(dirs):
            next_node = dir(*cur_node)
            if maze_cp[next_node[0]][next_node[1]] == 0:   #找到一个能走的方向
                stack.append(next_node)
                direction.append(id_d[index_d])#根据索引添加走法到direction列表
                maze_cp[next_node[0]][next_node[1]] = 2  # 2表示已经走过的点
                break
        else: #如果一个方向也找不到
            stack.pop()#找不到就退回之前的那一步
            direction.pop()
    else:
        print("无路可走")
        return False
'''
功能：输出迷宫图
'''
def print_maze(maze_ip):
    for ind in range(len(maze_ip)):
        for i in maze_ip[ind]:
            if i == 1:
              print("*", end=" ")#将不能走的1输出为*，方便看
            elif i == 0:
              print("-", end=" ")#将可以走的0输出为-，方便看
        print()
'''
功能：输出路线图
'''    
def print_maze_done(maze_ip):
    print("原迷宫：")
    print_maze(maze_ip)
    print("路线：")
    for ind in range(len(maze_ip)):
        for ind1, i in enumerate(maze_ip[ind]):
            if i == 1:#1不允许走
              print("*", end=" ")
            elif i == 0:#0允许走
              bool_ = False
              for data_ in stack_cp:#遍历寻找在路线里的点和当前所在的点是否匹配
                if data_ == (ind, ind1):
                  bool_ = True#找到了
                  break#找到了就退出
              if bool_:
                print("@", end=" ")#找到了就标@
              else:
                print("-", end=" ")#找不到说明这个点不是路线中的点，标-
        print()
    
print("走迷宫吼")
print_maze(maze)#打印迷宫图
solve_maze(1,1,8,8,maze) #1，1开始到8，8为结束点
print_maze_done(maze_cp1)#打印路线图

运行结果

最后

这篇blog里写的程序得到的路线不是最优路线，但是懒得研究了

谢谢啦

EOF