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

迷宫问题:一个由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%