浦发一连到底(Python迷宫程序)

发表于 | 分类于 | 评论数： | 阅读次数：
本文字数： 2k | 阅读时长 ≈ 4 分钟

迷宫问题：一个由0或1构成的二维数组中，假设1是可以移动到的点，0是不能移动到的点，如何从数组中间一个值为1的点出发，每一只能朝上下左右四个方向移动一个单位，当移动到二维数组的边缘，即可得到问题的解，类似的问题都可以称为迷宫问题。

浦发一连到底的游戏也类似于迷宫问题

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
# 判断坐标的有效性，如果超出数组边界或是不满足值为1的条件，说明该点无效返回False，否则返回True。
def valid(maze,x,y):
    if (x>=0 and x<len(maze) and y>=0 and y<len(maze[0]) and maze[x][y]==1):
        return True
    else:
        return False

#检测是否走完
def check(maze):
    i=0
    for ma in maze:
        for m in ma:
            if m==1:
                i=i+1
    if i>=1:
        return False
    else:
        return True


i=1
it=2

def walk(maze,x,y):
    global it
    global i
    global matrix
    # print(x,y)
    # 如果位置是迷宫的出口，说明成功走出迷宫
    # print(np.array(maze))

    if(check(maze)):
        print("successful!")
        # print(maze)

        if i==1:
            1+1
            ka = -1
            for ma in maze:
                k=0
                ka = ka+1
                for m in ma:
                    # print(ka,k,m)
                    matrix[ka][k]=m
                    k=k+1
                    if k==5:
                        k=0
        # print(matrix)
        i=i+1
        return False
    # 递归主体实现
    if valid(maze,x,y):
        # p1 = plt.scatter(x+1, y+1, marker='x', color='g', label='1', s=30)
        # print(x,y)
        # matrix[x][y]=it
        # it = it + 1
        maze[x][y]=it  # 做标记，防止折回
        # 针对四个方向依试探，如果失败，撤销一步
        it=it+1
        if not walk(maze,x-1,y):
            #左
            maze[x][y]=1
            it = it - 1
        elif not walk(maze,x,y-1):
            #上
            maze[x][y]=1
            it = it - 1
        elif not walk(maze,x+1,y):
            #右
            maze[x][y]=1
            it = it - 1
        elif not walk(maze,x,y+1):
            #下
            maze[x][y]=1
            it = it - 1
        else:
            walk(maze, x, y)
            maze[x][y] = 1
            it = it - 1
            # print('1')
            # return False  # 无路可走说明，没有解
    return True
0%