-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy path18b.py
176 lines (152 loc) · 8.82 KB
/
18b.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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
import collections
s = """#################################################################################
#.........#.............#.......#.....#.#.....................#...#..c#.........#
#.###.#####.#######.#####.###.#.#.###.#.#.#######.###########.#.#.###.#.#####.#.#
#.#.#.#e..#...#.#...#.....#.#.#...#.....#..b#...#.#.........#...#.....#.#.T..r#.#
#.#.#.#.#.###.#.#.#.#.#####.#.#############.#.###.#.#####.#.#.#######.#.#.#######
#.#...#.#...#...#.#.#.#.....#.........K.#.#.#...#.#.#...#.#...#...#...#.#.......#
#.###.#.###.#.###.#.#.#.###.###########.#.#.###.#.###.#.#.#####.#.#.###.#######.#
#...#.#...#...#...#.#...#.#...#.....#...#.#.#...#.....#.#.#.....#.#...#.#.#.....#
###.#.###.#####.#########.###.#.###.#.#.#.#.#.#.#######.#.#O#####.#####.#.#.###.#
#...#.#.#...#.#.............#.#.#...#.#.#...#x#.#.....#.#.#...#z#.....#.#.#.#...#
#.###.#R###.#.#####.#.#######.#.#.###.#.#.###.#.#.###.#.#.###.#.#####.#.#.#.#####
#.#...#...#.#.....#.#.#.....#.#.#.#...#.#...#.#...#...#.#.#.......#...#...#.....#
#.#.#####.#.###.#.#.#.#.###.#.#.#.#.#######.#.#####L###.#.#.#####.#.#####.#####.#
#.#.......#...#.#.#.#.#...#...#.#.#...Y.#.#.#...#.....#.#.#.#...#.#.......#....q#
#.###########.#.#.#.#####.#######.#####.#.#.###.#######.###.#.#.#.#########.###.#
#...#.......#.#.#.#...#...#..h..#.....#.#.......#.....#...#.#.#.#.#.......#.#...#
#.#.#.#####.#.#.#.###.#.###.###.###.###.#######.#.###.###.#.#.#.#.#.#######.#.###
#.#.....#...#.#.#...#.#.#...#.....#.#...#...#...#...#...#...#.#.#.#.#.......#.#.#
#########.###.#####.#.#.#F#.#####.#.#.###.#.###.###.###.#.###.#.#.#.#.#######.#.#
#.........#...#.....#...#.#.#...#...#.#s#.#...#.#...#...#.#...#.#.#.#.#...#...#.#
#.#####.###.###.#.#####.#.###.#.###.#.#.#.###.###.###.#####.###.#.#.#.#.###.###.#
#..d#...#...#...#.#...#...#...#.#...#.#.#.#.#.....#.#.......#...#...#.#...#.#...#
#.#.#####.###.#.###.#######.###.#####.#.#.#.#######.#############.###.#.#.#.###.#
#.#.....#...#.#...#.........#.#.......#.#.......#.....#.....#.....#...#.#.#.....#
#.#####.###.#####.###########.#########.#######.#.###.###.#.#####.#.#####.#####.#
#.#...#...#...#...#.......#...........#.#.....#...#...#...#.....#.#...#.....#...#
#.#.###.#.###.#.#.#.#####.###.#######.#.#.###.#####.###.#######.#####.#.#####.###
#.#.#...#.#.#.#.#...#.....#...#.......#.#.#.#.....#...#.#.....#.#.....#.........#
#.#.#.###.#.#.#.#####.#####.#####.#####.#.#.###.#.###.#.#.#.###.#.#.#######.#####
#...#.#.#...#.#...#.#.#...#.....#.#.....#.....#.#...#...#.#.#...#.#j#.....#.#.W.#
#####.#.###.#.###.#.#.#.#.#####.#.###.#.#####.#.#########.###.###.###.###.###.#.#
#...#.#.....#.#...#.#.#.#.......#.....#.#.#...#.........#.....#.....#...#...#.#.#
#.#.#.#####.#.#.###.#.#.###############.#.#.#########.###.#########.#.#####.#.#.#
#.#...#...#.#.#w..#...#...#...........#.#.#.#.......#...#...#.....#...#.V.#...#.#
#.#####.#.###.###.#.###.#.#.###########.#.#.#####.#.###.###.###.#M#####.#.#####.#
#.....#.#...#.....#.#.#.#.#.A.#...#.....#.#.......#...#...#...#.#.......#.......#
#####.#.###.#######.#.#.#.#.#.#.#.#.#####.###########.###.###.#.###############.#
#.....#.#.#.......#.#...#.#.#...#.#.....#...#.......#.#.#.#...#.....#.#.....#...#
#.#####.#.#######.#.#####.#.#####.#####.#.#.#.###.###.#.#.#.#######.#.#.###.#.###
#............v..#.........#.....#......@#@#.....#.......#...........#.....#.....#
#################################################################################
#.#.....G.....#.....#.......#.........#@#@......#.......#...........#.......#...#
#.#.###.#####.#####.#.#####.#.###.###.#.#.#####.#####.#.#######.###.#.###.#.###.#
#.#.#.#.....#.......#.#...#...#.#.#.....#.#...#......a#.......#...#.#.#...#.#...#
#.#.#.#####.#######.#.#.#.#####.#.#####.#.#.#.###############.###.#.#.#.###.#.#.#
#.#..n....#.#.......#.#.#...#...#.....#.#.#.#...#.....#.....#...#.#...#...#.#.#.#
#.#######.#.#########.#.###.#.#######.#.#.#.#####.#.###.#.#.###.#########P#.#.###
#...#.#...#...#u..#...#.#...#.......#.#.#.#...#...#.....#.#...#.....#...#.#.#...#
#.#.#.#.#####.#.#.#.###.###.###.###.#.#.#.###.#.#########.###.#####.#.#U#.#.###.#
#.#...#p..#.#...#...#.....#.....#...#.#.#...#.#.#.....#...#...#...#...#.#.#...#.#
#.###.###.#.###########.#.###########.#####.#.#.###.#.#.###.###.#.#####.#.###.#.#
#...#.#...#...#.......#.#.#..k..#...#...#...#.#.#...#.#.#...#...#...#...#...#.#.#
#.#.###.###.#.###.###.###.#.###.#.#.###.#.###.#.#.###C#Z###.#.#####.#.###.#.#.#.#
#.#.........#.....#.#.#...#.#...#.#...#.#...#.#.#.#...#...#.#.....#.#...#.#.#.#.#
#.#################.#.#.###.#.###.###.#.#.#.#.#.#.#.#####.#.###.###.###.###.#.#.#
#m....#...........#.#...#...#...#...#.#.#.#.#.#.#.#.#.....#...#.#...#..g#.N.#...#
#.#####.#########.#.###.#.#####.###.#.#.###.#.#.#B#.#.#########.#.###.###.#####.#
#.#.....#.....#...#.....#.#...#.#...#...#...#.....#.#.......#...#...#...#.#i..#.#
###.#######.###.#########.#.###.#.#######.#########.#######.#.#####.###.#.#.#.#.#
#...#.......#...#....y....#...#.#.#.....#.#...S.#...#.....#.......#.#...#.#.#.#.#
#.###.#####.#.#.#.#########.#.#.#.#.###.#.#.###.#.###.###.#####.###.#.###.#.#.#.#
#...#.#.#...#.#.#.....#...#.#...#.....#.#.....#.#...#.#.....#.#.#...#.....#.#.#.#
###.#.#.#.###.#########.#.#.#####.#####.#######.###X#.#######.###.#.#######.###.#
#...#.#.#...#...........#.#...#...#.....#...#...#...#.#.......#...#.....#.......#
#Q###.#.###.#####.###########.#.###.###.#.#.#.#####.#.#.#######.#########.#######
#.....#...#.#...#.........#...#.#...#.#.#.#.#.....#...#...#.....#.......#.......#
#######.###.#.###########.#.#####.###.#.#.#.#####.###.###.#####.#D#####.#######.#
#.....#...#.#.......#...#...#.....#.....#.#.#...#.#....l#...#...#.#...#.......#.#
###.#.###.#.###.###.###.#####.#.#########.#.#.###.#########.#.#.#.###.#######.#.#
#...#...#.#.....#...#.......#.#.........#.#.#.#...#...#...#.#.#.#...#.......#...#
#.#####.#.#######.###.#######.#########.#.#.#.#.###.#.#.#.#.#.#.###.#.#####.#####
#.#..t#.#.....#...#.............#.....#.#.#.#.#.....#...#...#.#.#...#.#...#.....#
#.###.#.#.#####.###.###########.#.#.###.#.#.#.###############.#.#.#####.#.#####.#
#...#.....#...#.#.....#.......#...#.#...#.#.........#.........#.#.......#.#.....#
#E#.#.#####.#.#.#####.#.#####.#####.#.###.###.#######.#####.#############.#.#####
#.#.#...#...#.#...#...#.#...#...#...#...#...#.#.....#.#...#.........#.....#.#...#
###.#####.###I###.#.###.#.#.###.#####.#.#.#.###.###.#.#.#######.#####.#####.#.#.#
#...#...#...#...#.#.#...#.#...#.#...#.#.#.#..f..#.#...#.....#...#.....#...#...#.#
#.###.#.###.#.###.###.###.#####.#.#.###.#.#######.#########.#.###.#####.#.#####.#
#.J...#.....#.........#...........#.....#.............H....o#...........#.......#
#################################################################################"""
l = s.split('\n')
keys = [False] * 26
starts = []
for i in range(len(l)):
for j in range(len(l[i])):
if l[i][j] == '@':
starts.append((i,j))
posis = [0] * 26
for i in range(len(l)):
for j in range(len(l[i])):
if 'a' <= l[i][j] <= 'z':
posis[ord(l[i][j]) - ord('a')] = (i,j)
visited = set()
visited.add((i,j))
dirX = [0,0,-1,1]
dirY = [-1,1,0,0]
reach = dict()
reach[tuple([()]) + tuple(starts)] = 0
tupleQ = collections.deque()
tupleQ.append(tuple([()]) + tuple(starts))
BEST = 10**10
count = 0
while tupleQ:
nexTup = tupleQ.popleft()
count += 1
if count % 100 == 0:
print(nexTup, reach[nexTup])
if len(nexTup[0]) == 26:
BEST = min(BEST, reach[nexTup])
continue
queue = collections.deque()
for i in range(4):
queue.append(nexTup[i + 1] + (reach[nexTup], i + 1))
keys = [False] * 26
visited = set()
for c in nexTup[0]:
keys[ord(c) - ord('a')] = True
###
while queue:
nex = queue.popleft()
for i in range(4):
newX = nex[0] + dirX[i]
newY = nex[1] + dirY[i]
dist = nex[2] + 1
change = nex[3]
if (newX, newY) in visited:
pass
else:
visited.add((newX,newY))
v = l[newX][newY]
if v == '#':
pass
elif v == '.' or v == '@':
queue.append((newX, newY, dist, change))
elif 'a' <= v <= 'z':
if keys[ord(v) - 97]:
queue.append((newX, newY, dist, change))
else:
lis = [tuple(sorted(nexTup[0] + tuple(v))), nexTup[1], nexTup[2], nexTup[3], nexTup[4]]
lis[change] = (newX, newY)
newTup = tuple(lis)
if newTup in reach:
reach[newTup] = min(dist, reach[newTup])
else:
reach[newTup] = dist
tupleQ.append(newTup)
elif 'A' <= v <= 'Z':
if keys[ord(v) - 65]:
queue.append((newX, newY, dist, change))
###