-
Notifications
You must be signed in to change notification settings - Fork 0
/
maze.py
59 lines (50 loc) · 1.35 KB
/
maze.py
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
debug = False
def allAdj(x, n):
adj = []
#left
if x[0] > 0:
adj.append((x[0]-1, x[1]))
#right
if x[0] < n-1:
adj.append((x[0]+1, x[1]))
#top
if x[1] > 0:
adj.append((x[0], x[1]-1))
#bottom
if x[1] < n-1:
adj.append((x[0], x[1]+1))
return adj
def computeSP(maze, S, D):
n = len(maze)
path = [[(-1, -1) for x in range(n)] for x in range(n)]
dist = [[n*n for x in range(n)] for x in range(n)]
dist[S[0]][S[1]] = 0
path[S[0]][S[1]] = S
changeFlag = True
while changeFlag:
if debug: print dist
changeFlag = False
for x in range(n):
for y in range(n):
adj = allAdj((x,y), n)
for a in adj:
if dist[a[0]][a[1]] + 1 < dist[x][y] and maze[a[0]][a[1]] == 0 and maze[x][y] == 0:
dist[x][y] = dist[a[0]][a[1]] + 1
path[x][y] = a
changeFlag = True
if debug: print 'path: ', path
print 'distance = ', dist[D[0]][D[1]]
P = D
route = [D]
while not P == S:
P = path[P[0]][P[1]]
route.insert(0, P)
print route
maze = [[0, 1, 0, 0, 0],
[0, 1, 0, 0, 0],
[0, 1, 0, 1, 0],
[0, 1, 1, 0, 0],
[0, 0, 0, 0, 0],]
S = (0,0)
D = (2,2)
computeSP(maze, S, D)