-
Notifications
You must be signed in to change notification settings - Fork 3
/
main.go
405 lines (378 loc) · 17.7 KB
/
main.go
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
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
package main
import (
"fmt"
"math"
"strings"
)
func main() {
part1()
part2()
}
func part1() {
lines := strings.Split(input, "\n")
var startPos [2]int
var doorPos [26][2]int
var keyPos [26][2]int
for i, line := range lines {
for j := 0; j < len(line); j++ {
if line[j] == '@' {
startPos = [2]int{i, j}
} else if line[j] >= 'a' && line[j] <= 'z' {
keyPos[line[j]-'a'] = [2]int{i, j}
} else if line[j] >= 'A' && line[j] <= 'Z' {
doorPos[line[j]-'A'] = [2]int{i, j}
}
}
}
pmemo := map[[4]int]int{}
pathFind := func(pos [2]int, keys int, key int) int {
pkey := [4]int{pos[0], pos[1], keys, key}
if v, ok := pmemo[pkey]; ok {
return v
}
work := [][3]int{{pos[0], pos[1], 0}}
seen := map[[2]int]bool{}
target := keyPos[key]
dirs := [][2]int{{1, 0}, {0, 1}, {-1, 0}, {0, -1}}
for len(work) > 0 {
w := work[0]
work = work[1:]
k := [2]int{w[0], w[1]}
if k == target {
pmemo[pkey] = w[2]
return w[2]
}
if seen[k] {
continue
}
seen[k] = true
for _, dir := range dirs {
w2 := [3]int{w[0] + dir[0], w[1] + dir[1], w[2] + 1}
if w2[0] < 0 || w2[0] >= len(lines) || w2[1] < 0 || w2[1] >= len(lines[0]) {
continue
}
c := lines[w2[0]][w2[1]]
if c == '#' {
continue
}
b := 1 << uint(c-'a')
if c >= 'a' && c <= 'z' && int(c-'a') != key && (keys&b) == 0 {
continue
}
b = 1 << uint(c-'A')
if c >= 'A' && c <= 'Z' && (keys&b) == 0 {
continue
}
work = append(work, w2)
}
}
pmemo[pkey] = -1
return -1
}
min := math.MaxInt64
mins := map[[3]int]int{}
var search func([2]int, int, int)
search = func(pos [2]int, keys int, plen int) {
if keys == (1<<26)-1 {
if plen < min {
min = plen
}
return
}
if plen >= min {
return
}
key := [3]int{pos[0], pos[1], keys}
if v, ok := mins[key]; ok && v <= plen {
return
}
mins[key] = plen
for nextKey := 0; nextKey < 26; nextKey++ {
bit := 1 << uint(nextKey)
if keys&bit != 0 {
continue
}
aplen := pathFind(pos, keys, nextKey)
if aplen == -1 {
continue
}
search(keyPos[nextKey], keys|bit, plen+aplen)
}
}
search(startPos, 0, 0)
fmt.Println(min)
}
func part2() {
lines := strings.Split(input2, "\n")
spcount := 0
var startPoss [4][2]int
var doorPos [26][2]int
var keyPos [26][2]int
for i, line := range lines {
for j := 0; j < len(line); j++ {
if line[j] == '@' {
startPoss[spcount] = [2]int{i, j}
spcount++
} else if line[j] >= 'a' && line[j] <= 'z' {
keyPos[line[j]-'a'] = [2]int{i, j}
} else if line[j] >= 'A' && line[j] <= 'Z' {
doorPos[line[j]-'A'] = [2]int{i, j}
}
}
}
pmemo := map[[4]int]int{}
pathFind := func(pos [2]int, keys int, key int) int {
pkey := [4]int{pos[0], pos[1], keys, key}
if v, ok := pmemo[pkey]; ok {
return v
}
work := [][3]int{{pos[0], pos[1], 0}}
seen := map[[2]int]bool{}
target := keyPos[key]
dirs := [][2]int{{1, 0}, {0, 1}, {-1, 0}, {0, -1}}
for len(work) > 0 {
w := work[0]
work = work[1:]
k := [2]int{w[0], w[1]}
if k == target {
pmemo[pkey] = w[2]
return w[2]
}
if seen[k] {
continue
}
seen[k] = true
for _, dir := range dirs {
w2 := [3]int{w[0] + dir[0], w[1] + dir[1], w[2] + 1}
if w2[0] < 0 || w2[0] >= len(lines) || w2[1] < 0 || w2[1] >= len(lines[0]) {
continue
}
c := lines[w2[0]][w2[1]]
if c == '#' {
continue
}
b := 1 << uint(c-'a')
if c >= 'a' && c <= 'z' && int(c-'a') != key && (keys&b) == 0 {
continue
}
b = 1 << uint(c-'A')
if c >= 'A' && c <= 'Z' && (keys&b) == 0 {
continue
}
work = append(work, w2)
}
}
pmemo[pkey] = -1
return -1
}
keySegs := [4]int{}
for i := 0; i < 26; i++ {
for j := 0; j < 4; j++ {
if pathFind(startPoss[j], (1<<26)-1, i) != -1 {
keySegs[j] |= (1 << uint(i))
}
}
}
min := math.MaxInt64
mins := map[[9]int]int{}
var search func([4][2]int, int, int)
search = func(pos [4][2]int, keys int, plen int) {
if keys == (1<<26)-1 {
if plen < min {
min = plen
}
return
}
if plen >= min {
return
}
key := [9]int{pos[0][0], pos[0][1], pos[1][0], pos[1][1], pos[2][0], pos[2][1], pos[3][0], pos[3][1], keys}
if v, ok := mins[key]; ok && v <= plen {
return
}
mins[key] = plen
for nextKey := 0; nextKey < 26; nextKey++ {
bit := 1 << uint(nextKey)
if keys&bit != 0 {
continue
}
var bi int
for i := 0; i < 4; i++ {
if keySegs[i]&bit != 0 {
bi = i
}
}
npos := pos
npos[bi] = keyPos[nextKey]
aplen := pathFind(pos[bi], keys, nextKey)
if aplen == -1 {
continue
}
search(npos, keys|bit, plen+aplen)
}
}
search(startPoss, 0, 0)
fmt.Println(min)
}
const input = `#################################################################################
#.............#..o..........#...........#...............#b......#...#.........#.#
#.#######.#.#.#.#.#########.###.#######.###.#########.###.###.###.#.#C#####.#.#.#
#.#...A.#.#.#.#.#.#w....#.#...#..e#.....#...#.....#...#...#...#...#.#.....#.#k..#
#.#.###.###.#.###.###.#.#.###.#####.###.#.###.#####.###.###.###.###.#####.#.###.#
#.#...#.....#...#.#...#.....#.....#...#.#...#.#...#.#...#.#.....#.#.....#.#.#...#
#.###.#########.#.#.#######.#####.###.#.###.#.#.#.#.#.###.#######.###.#.#.#.#####
#...#.#...........#.......#.....#.....#.#...#...#.#.#.......#.....#...#.#.#.#...#
###.#.###.#############.#.#############.#.###.###.#P#######.###.#.#.###.#.#.#.#.#
#...#...#.#.....#.....#.#.....#...#.....#.#.....#.......#...#...#.#.#...#.#...#.#
#.#####.#.#.###.#.###.#######.#.#.#.#####.###############.###.#####.#.###.#####.#
#.....#.#.#.#.#.#...#.#.....#.#.#.#.....#.......#.......#.#.......#.#...#.#...#.#
###.###.#.#.#.#.###.#.#.###.#.#.#.#####.#.#####.#.#####.#.#######.#.###.#.#.###.#
#...#...#.#...#.#...#.#.#...#...#.....#.#.#.#...#.#.#...#...#.....#.#...#.#.#...#
#.###.#######.#.#.###.#.###.#.#####.###.#.#.#.#.#.#.#.#####.#.###.#D###.#.#.#.###
#...#.....#...#.....#.#...#.#.#...#.#...#...#.#.#...#.....#.#.#.X.#...#.#...#...#
###.#####.#.#####.###.###.#.###.#.#.#.#######.#.###.#####.#.#.###.###.#####.###.#
#.#.....#...#...#.#...#.#.#.#...#.#.#...#.....#.#.#.#...#.#.#...#...#...#...#...#
#.#####.#####.#.###.#.#.#.#.#.###.#.###.#.#####.#.#.#.#.#.#.###.#.#####.#.###.###
#.#...#.#.....#.....#...#.#...#...#.....#.#.....#.#.#.#.#.......#.#...#.....#...#
#.#.#.#.#.###.#########.#.#####.#######.#.#.#####.#.###.#########.#.#.#########.#
#...#...#...#.#...#...#.#.#...#.......#.#.#.....#.#.#.....#...#...#.#.........#i#
#.#####.###.#.#.#.#.#####.#.#########.#.#.#####.#.#.#.#####.#######.#########.#.#
#.#...#...#.#.#.#...#.....#.........#.#.#.....#...#...#n..#..f..#.Z.#...W...#.#.#
#K#Y#.#.###.#.#.#####.#####.###.#####.#.#####.#####.###.#.#####.#.###.#.#####.#.#
#.#.#.#.#...#.#.#.#...#...#.#.#.#...#.#.#.....#.....#...#.......#.#.#.#......h#.#
#.#.#.###.#.###.#.#.#.###.#.#.#.#.#.#.#.#.#J###.#####.###########.#.#.#########.#
#.#.#.....#.#...#...#...#...#.#.#.#...#.#.#.#...#...#.....#...#g..#.#.#...#.....#
###.#######.#.###.#####.#.###.#.#.#######.###.#####.#####.#.#.#.###.#.#.###.###.#
#...#.....#.#.#...#.....#.....#.#.......#...#.#.......#.#...#...#.....#.....#...#
#.#####.###.#.#.###.#########.#.#######.#.#.#.###.###.#.#########.#####.#####.###
#.....#.....#d#...#.#...#...#.#.......#.#.#.#...#...#.#.......#.#.#...#...#.#...#
#.###.#.#####.###.#.#.#.#.#.#.###.#####.###.###.###.#.###.###.#.#.###.###.#.###.#
#.#...#...#.#.#...#.#.#.#.#...#.#.....#.#...#.#.....#...#.#.#...#...#.....#.#...#
#.#.#####.#.#.#####.#.#.#.#####.#####.#.#.#.#.#########.#.#.###.###.#####.#.#.###
#.#.....#.#.#...#...#.#.#...#.......#.#.#.#.......#...#...#...#...#.....#.#.#...#
#.#####V#.#.###.#.###.#.###.#.#####.#.#.#.#######.#.#.#####.#.###.#####.#.#U###.#
#.....#.#.....#...#...#...#.#.....#.#...#...#.....#.#.......#.#...#..v#.#.....#.#
#####.#.###########.#######.#####.#.#####.#.#######.#####.#####.#####.#.#######.#
#.....#...........................#.......#.............#.........R...#l........#
#######################################.@.#######################################
#.............#......r..#.......#...........#.........#...#.......#.....#.#.....#
#.###########.#######.###.#.###.#.#####.#.###.#######.#.#.#.###.###.#.#.#.#.#.###
#...#.......#.......#.....#.#.#...#...#.#.#...#.....#...#.#...#.....#y#...#.#...#
###.#.###.#.#######.#.#####.#.#######.#.#.#.###.###.#####.###.#######.###.#.###Q#
#...#.#...#.#.......#.#.....#.......#.#.#...#...#...#...#...#...#...#...#.#.#.#.#
#.###.#.#.###.#######.#.#######.###.#.#.#.###.#####.#.#.###.###.#.#.###.#.#.#.#.#
#.#...#.#.#.........#.#...#.....#.....#.#.#...#...#...#.#.#.....#.#.#...#.#...#.#
#.#.###.###.#######.#####.#.#.#########.#.###.#.#.#####.#.#######.#.#.#######.#.#
#q#...#.....#.....#.....#.#.#.#...#.....#...#...#.#...#.........#.#.#.#.......#.#
#.#######.###.###.#####.#.#.###.#.#.#######.#.###.#.#.#########.#.#.#.#.#######.#
#.#.....#...#.#.#.#...#.#.#.#...#.#.....#..j#.#...#.#.....#.....#.#.#.....#.....#
#.#.###.#####.#.#.###.#.#.#.#.###.#####.#.###.#.###.#####.###.###.#.#######.###.#
#.#.#.#...#...#.#.#...#...#.#...#.......#.#.#.#.....#...#...#...#.#.......#...#.#
#.#L#.###.#.###.#.#.#######.###.#########.#.#.#########.###.###.#.#######.###S#.#
#.#...#.#.#.#...#.#.#...#.......#...#...#.#.............#.#.#.#.#.#.....#...#.#.#
#.###.#.#.#.###.#.#.#.#.#.#######.#.#.#.#.#.###########.#.#.#.#.#.###.#.###.#.#.#
#...#...#...#...#.#.#.#.........#.#.#.#.#.#.#.......#.#.#.#.#...#...#.#...#.#.#.#
#.#.###.#####.#.#H#.#.#########.#.#.#N#.#.#.#.#####.#.#.#.#.#######.###.#.#.#.#.#
#.#.#...#.....#.#.#.....#...#...#.#...#.#.#.#.#...#.#.....#.#.....#...#.#.#...#.#
###.#.###.#.#####.#.#####.#.#.###.#####.#.###.#.#.#.#.#####.#.###.###.#.#######.#
#...#...#.#...#...#.#.T...#.#.#.F.#.#...#.....#.#.#.#...#...#.#...#...#...#...#.#
#.#####.#.###.#.###########.###.###.#.#########.#.#.###.#.#.###.###.###.#.#.#.#.#
#.....#.#.#u..#..z........#....t#.G...#.#.......#.#.#...#.#...#.#...#...#...#...#
###.#.#.###.###########.#########.#####.#.#####.#.#.#####.#.###.#.#######.#######
#...#s#...#.....#.....#.........#.#.....#.....#.#.#.....#.#.#...#.......#...#...#
#.###.###.###.#.#.###.#######.###.#.###########.#######.#.#.#.###.#####.#####.#.#
#.#.....#...#.#.....#.......#.....#.....#.....#.......#.#.#.#...#.#...#...#...#.#
#.#########.###############.###########.#.###.#####.###.#.#####.#.#.#####.#.###.#
#.#x......#.#...#...........#...........#.#.........#...#.#.....#...#.....#.#...#
#.#.#####.#I#.#.#.#########.#####.#####.#.###########.###.#.#######.#.#####.#.###
#.#...#...#...#...#.....#.#.#...#...#...#.............#...#.....#.#.#.......#.O.#
#.###.#.#############.#.#.#.#.#.###.#.###.###############.#####.#.#.#######.###.#
#...#.#.....#...#.....#...#.#.#.....#.#.#.#...#...#.....#..m#...#...#.....#.#...#
#.###.###.#.#.#.###.#######.#.#######.#.#.#.#.#.#.#.###.###.#.#######.###.#.#.###
#.#...#.#.#...#.....#.....#...#.....#...#.#.#...#.#...#.#...#.....#...#...#.#...#
#.#M###.#.###########.###.#####.###.###.#.#.#####.###.#.#.#######.#.###.#######.#
#.#...#.#...#..a..#...#.#.....#.#.....#.#p..#...#...#.#.#.#.......#.#...#.....#.#
#.###.#.###.#.###.#.###.###.###.#.#####.#####.#####.#.#.#.#.#######.#.###.###.#.#
#.........#...B.#.........#.....#.......#.............#...#.......E.#.....#....c#
#################################################################################`
const input2 = `#################################################################################
#.............#..o..........#...........#...............#b......#...#.........#.#
#.#######.#.#.#.#.#########.###.#######.###.#########.###.###.###.#.#C#####.#.#.#
#.#...A.#.#.#.#.#.#w....#.#...#..e#.....#...#.....#...#...#...#...#.#.....#.#k..#
#.#.###.###.#.###.###.#.#.###.#####.###.#.###.#####.###.###.###.###.#####.#.###.#
#.#...#.....#...#.#...#.....#.....#...#.#...#.#...#.#...#.#.....#.#.....#.#.#...#
#.###.#########.#.#.#######.#####.###.#.###.#.#.#.#.#.###.#######.###.#.#.#.#####
#...#.#...........#.......#.....#.....#.#...#...#.#.#.......#.....#...#.#.#.#...#
###.#.###.#############.#.#############.#.###.###.#P#######.###.#.#.###.#.#.#.#.#
#...#...#.#.....#.....#.#.....#...#.....#.#.....#.......#...#...#.#.#...#.#...#.#
#.#####.#.#.###.#.###.#######.#.#.#.#####.###############.###.#####.#.###.#####.#
#.....#.#.#.#.#.#...#.#.....#.#.#.#.....#.......#.......#.#.......#.#...#.#...#.#
###.###.#.#.#.#.###.#.#.###.#.#.#.#####.#.#####.#.#####.#.#######.#.###.#.#.###.#
#...#...#.#...#.#...#.#.#...#...#.....#.#.#.#...#.#.#...#...#.....#.#...#.#.#...#
#.###.#######.#.#.###.#.###.#.#####.###.#.#.#.#.#.#.#.#####.#.###.#D###.#.#.#.###
#...#.....#...#.....#.#...#.#.#...#.#...#...#.#.#...#.....#.#.#.X.#...#.#...#...#
###.#####.#.#####.###.###.#.###.#.#.#.#######.#.###.#####.#.#.###.###.#####.###.#
#.#.....#...#...#.#...#.#.#.#...#.#.#...#.....#.#.#.#...#.#.#...#...#...#...#...#
#.#####.#####.#.###.#.#.#.#.#.###.#.###.#.#####.#.#.#.#.#.#.###.#.#####.#.###.###
#.#...#.#.....#.....#...#.#...#...#.....#.#.....#.#.#.#.#.......#.#...#.....#...#
#.#.#.#.#.###.#########.#.#####.#######.#.#.#####.#.###.#########.#.#.#########.#
#...#...#...#.#...#...#.#.#...#.......#.#.#.....#.#.#.....#...#...#.#.........#i#
#.#####.###.#.#.#.#.#####.#.#########.#.#.#####.#.#.#.#####.#######.#########.#.#
#.#...#...#.#.#.#...#.....#.........#.#.#.....#...#...#n..#..f..#.Z.#...W...#.#.#
#K#Y#.#.###.#.#.#####.#####.###.#####.#.#####.#####.###.#.#####.#.###.#.#####.#.#
#.#.#.#.#...#.#.#.#...#...#.#.#.#...#.#.#.....#.....#...#.......#.#.#.#......h#.#
#.#.#.###.#.###.#.#.#.###.#.#.#.#.#.#.#.#.#J###.#####.###########.#.#.#########.#
#.#.#.....#.#...#...#...#...#.#.#.#...#.#.#.#...#...#.....#...#g..#.#.#...#.....#
###.#######.#.###.#####.#.###.#.#.#######.###.#####.#####.#.#.#.###.#.#.###.###.#
#...#.....#.#.#...#.....#.....#.#.......#...#.#.......#.#...#...#.....#.....#...#
#.#####.###.#.#.###.#########.#.#######.#.#.#.###.###.#.#########.#####.#####.###
#.....#.....#d#...#.#...#...#.#.......#.#.#.#...#...#.#.......#.#.#...#...#.#...#
#.###.#.#####.###.#.#.#.#.#.#.###.#####.###.###.###.#.###.###.#.#.###.###.#.###.#
#.#...#...#.#.#...#.#.#.#.#...#.#.....#.#...#.#.....#...#.#.#...#...#.....#.#...#
#.#.#####.#.#.#####.#.#.#.#####.#####.#.#.#.#.#########.#.#.###.###.#####.#.#.###
#.#.....#.#.#...#...#.#.#...#.......#.#.#.#.......#...#...#...#...#.....#.#.#...#
#.#####V#.#.###.#.###.#.###.#.#####.#.#.#.#######.#.#.#####.#.###.#####.#.#U###.#
#.....#.#.....#...#...#...#.#.....#.#...#...#.....#.#.......#.#...#..v#.#.....#.#
#####.#.###########.#######.#####.#.#####.#.#######.#####.#####.#####.#.#######.#
#.....#...........................#....@#@#.............#.........R...#l........#
#################################################################################
#.............#......r..#.......#......@#@..#.........#...#.......#.....#.#.....#
#.###########.#######.###.#.###.#.#####.#.###.#######.#.#.#.###.###.#.#.#.#.#.###
#...#.......#.......#.....#.#.#...#...#.#.#...#.....#...#.#...#.....#y#...#.#...#
###.#.###.#.#######.#.#####.#.#######.#.#.#.###.###.#####.###.#######.###.#.###Q#
#...#.#...#.#.......#.#.....#.......#.#.#...#...#...#...#...#...#...#...#.#.#.#.#
#.###.#.#.###.#######.#.#######.###.#.#.#.###.#####.#.#.###.###.#.#.###.#.#.#.#.#
#.#...#.#.#.........#.#...#.....#.....#.#.#...#...#...#.#.#.....#.#.#...#.#...#.#
#.#.###.###.#######.#####.#.#.#########.#.###.#.#.#####.#.#######.#.#.#######.#.#
#q#...#.....#.....#.....#.#.#.#...#.....#...#...#.#...#.........#.#.#.#.......#.#
#.#######.###.###.#####.#.#.###.#.#.#######.#.###.#.#.#########.#.#.#.#.#######.#
#.#.....#...#.#.#.#...#.#.#.#...#.#.....#..j#.#...#.#.....#.....#.#.#.....#.....#
#.#.###.#####.#.#.###.#.#.#.#.###.#####.#.###.#.###.#####.###.###.#.#######.###.#
#.#.#.#...#...#.#.#...#...#.#...#.......#.#.#.#.....#...#...#...#.#.......#...#.#
#.#L#.###.#.###.#.#.#######.###.#########.#.#.#########.###.###.#.#######.###S#.#
#.#...#.#.#.#...#.#.#...#.......#...#...#.#.............#.#.#.#.#.#.....#...#.#.#
#.###.#.#.#.###.#.#.#.#.#.#######.#.#.#.#.#.###########.#.#.#.#.#.###.#.###.#.#.#
#...#...#...#...#.#.#.#.........#.#.#.#.#.#.#.......#.#.#.#.#...#...#.#...#.#.#.#
#.#.###.#####.#.#H#.#.#########.#.#.#N#.#.#.#.#####.#.#.#.#.#######.###.#.#.#.#.#
#.#.#...#.....#.#.#.....#...#...#.#...#.#.#.#.#...#.#.....#.#.....#...#.#.#...#.#
###.#.###.#.#####.#.#####.#.#.###.#####.#.###.#.#.#.#.#####.#.###.###.#.#######.#
#...#...#.#...#...#.#.T...#.#.#.F.#.#...#.....#.#.#.#...#...#.#...#...#...#...#.#
#.#####.#.###.#.###########.###.###.#.#########.#.#.###.#.#.###.###.###.#.#.#.#.#
#.....#.#.#u..#..z........#....t#.G...#.#.......#.#.#...#.#...#.#...#...#...#...#
###.#.#.###.###########.#########.#####.#.#####.#.#.#####.#.###.#.#######.#######
#...#s#...#.....#.....#.........#.#.....#.....#.#.#.....#.#.#...#.......#...#...#
#.###.###.###.#.#.###.#######.###.#.###########.#######.#.#.#.###.#####.#####.#.#
#.#.....#...#.#.....#.......#.....#.....#.....#.......#.#.#.#...#.#...#...#...#.#
#.#########.###############.###########.#.###.#####.###.#.#####.#.#.#####.#.###.#
#.#x......#.#...#...........#...........#.#.........#...#.#.....#...#.....#.#...#
#.#.#####.#I#.#.#.#########.#####.#####.#.###########.###.#.#######.#.#####.#.###
#.#...#...#...#...#.....#.#.#...#...#...#.............#...#.....#.#.#.......#.O.#
#.###.#.#############.#.#.#.#.#.###.#.###.###############.#####.#.#.#######.###.#
#...#.#.....#...#.....#...#.#.#.....#.#.#.#...#...#.....#..m#...#...#.....#.#...#
#.###.###.#.#.#.###.#######.#.#######.#.#.#.#.#.#.#.###.###.#.#######.###.#.#.###
#.#...#.#.#...#.....#.....#...#.....#...#.#.#...#.#...#.#...#.....#...#...#.#...#
#.#M###.#.###########.###.#####.###.###.#.#.#####.###.#.#.#######.#.###.#######.#
#.#...#.#...#..a..#...#.#.....#.#.....#.#p..#...#...#.#.#.#.......#.#...#.....#.#
#.###.#.###.#.###.#.###.###.###.#.#####.#####.#####.#.#.#.#.#######.#.###.###.#.#
#.........#...B.#.........#.....#.......#.............#...#.......E.#.....#....c#
#################################################################################`