-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathmap.py
83 lines (74 loc) · 4.11 KB
/
map.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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
from collections import defaultdict
"""
'#' for obstacle
'-' for no power points
'b' for the ghost barrier
"""
map_1 = [
['#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '-'],
['#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#', '-'],
['#', ' ', '#', '#', ' ', '#', '#', '#', ' ', '#', ' ', '#', '#', '#', ' ', '#', '#', ' ', '#', '-'],
['#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#', '-'],
['#', ' ', '#', '#', ' ', '#', ' ', '#', '#', '#', '#', '#', ' ', '#', ' ', '#', '#', ' ', '#', '-'],
['#', ' ', ' ', ' ', ' ', '#', ' ', ' ', ' ', '#', ' ', ' ', ' ', '#', ' ', ' ', ' ', ' ', '#', '-'],
['#', '#', '#', '#', ' ', '#', '#', '#', ' ', '#', ' ', '#', '#', '#', ' ', '#', '#', '#', '#', '-'],
['-', '-', '-', '#', ' ', '#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#', ' ', '#', '-', '-', '-', '-'],
['#', '#', '#', '#', ' ', '#', ' ', '#', '#', 'b', '#', '#', ' ', '#', ' ', '#', '#', '#', '#', '-'],
[' ', ' ', ' ', ' ', ' ', ' ', ' ', '#', '-', '-', '-', '#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '-'],
['#', '#', '#', '#', ' ', '#', ' ', '#', '#', '#', '#', '#', ' ', '#', ' ', '#', '#', '#', '#', '-'],
['-', '-', '-', '#', ' ', '#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#', ' ', '#', '-', '-', '-', '-'],
['#', '#', '#', '#', ' ', '#', ' ', '#', '#', '#', '#', '#', ' ', '#', ' ', '#', '#', '#', '#', '-'],
['#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#', '-'],
['#', ' ', '#', '#', ' ', '#', '#', '#', ' ', '#', ' ', '#', '#', '#', ' ', '#', '#', ' ', '#', '-'],
['#', ' ', ' ', '#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#', ' ', ' ', '#', '-'],
['#', '#', ' ', '#', ' ', '#', ' ', '#', '#', '#', '#', '#', ' ', '#', ' ', '#', ' ', '#', '#', '-'],
['#', ' ', ' ', ' ', ' ', '#', ' ', ' ', ' ', '#', ' ', ' ', ' ', '#', ' ', ' ', ' ', ' ', '#', '-'],
['#', ' ', '#', '#', '#', '#', '#', '#', ' ', '#', ' ', '#', '#', '#', '#', '#', '#', ' ', '#', '-'],
['#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#', '-'],
['#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '-'],
]
# Python program to convert Adjacency matrix
# representation to Adjacency List
def convert(m):
adj_list = defaultdict(list)
obstacles = ("#",)
for y_index in range(len(m)):
for x_index in range(len(m[y_index])):
if m[y_index][x_index] not in obstacles:
if x_index > 0: # check tile at the left
if m[y_index][x_index - 1] not in obstacles:
adj_list[(x_index, y_index)].append((x_index - 1, y_index))
if x_index < len(m[y_index]) - 1: # check tile at the right
if m[y_index][x_index + 1] not in obstacles:
adj_list[(x_index, y_index)].append((x_index + 1, y_index))
if x_index > 0: # check tile at the top
if m[y_index - 1][x_index] not in obstacles:
adj_list[(x_index, y_index)].append((x_index, y_index - 1))
if x_index < len(m[y_index]) - 1: # check tile at the bottom
if m[y_index + 1][x_index] not in obstacles:
adj_list[(x_index, y_index)].append((x_index, y_index + 1))
return adj_list
adjList_map_1 = convert(map_1)
# from collections import defaultdict
# # converts from adjacency matrix to adjacency list
# def convert(a):
# adjList = defaultdict(list)
# for i in range(len(a)):
# for j in range(len(a[i])):
# if
# if a[i][j]== " ":
# adjList[(i)].append(j)
# return adjList
#
# # driver code
# AdjList = convert(map_1)
# print(AdjList)
# print("Adjacency List:")
# # print the adjacency list
# for i in AdjList:
# print(i, end ="")
# for j in AdjList[i]:
# print(" -> {}".format(j), end ="")
# print()
#
# # This code is contributed by Muskan Kalra.