55 lines
1.5 KiB
Python
55 lines
1.5 KiB
Python
|
import sys
|
||
|
|
from grid import *
|
||
|
|
from collections import defaultdict as DD
|
||
|
|
from collections import deque
|
||
|
|
from math import inf
|
||
|
|
|
||
|
|
def BFS(start, end, G):
|
||
|
|
seats = set()
|
||
|
|
seen = DD(lambda:inf)
|
||
|
|
dq = deque()
|
||
|
|
path = set()
|
||
|
|
path.add(start)
|
||
|
|
dq.append((start, (1, 0), 0, path))
|
||
|
|
best = inf
|
||
|
|
while dq:
|
||
|
|
pos, dirn, score, path = dq.popleft()
|
||
|
|
if score > seen[(pos, dirn)] or score > best:
|
||
|
|
continue
|
||
|
|
seen[(pos, dirn)] = score
|
||
|
|
if pos == end:
|
||
|
|
if score < best:
|
||
|
|
best = score
|
||
|
|
seats = path
|
||
|
|
elif score == best:
|
||
|
|
seats.update(path)
|
||
|
|
continue
|
||
|
|
dx, dy = dirn
|
||
|
|
x, y = pos
|
||
|
|
npos = (x+dx, y+dy)
|
||
|
|
if get_in_grid(G,*npos) != '#': # can move fw
|
||
|
|
np = path.copy()
|
||
|
|
np.add(npos)
|
||
|
|
dq.append((npos, dirn, score+1, np))
|
||
|
|
# turn 90°, both sides
|
||
|
|
ndy = dx
|
||
|
|
ndx = dy
|
||
|
|
np = path.copy()
|
||
|
|
dq.append((pos, (ndx, ndy), score+1000, np))
|
||
|
|
np = path.copy()
|
||
|
|
dq.append((pos, (-ndx, -ndy), score+1000, np))
|
||
|
|
return best, seats
|
||
|
|
|
||
|
|
L = sys.stdin.read().strip().split('\n')
|
||
|
|
G = [list(l) for l in L]
|
||
|
|
start = end = (-1, -1) # must init with correct type for codon
|
||
|
|
for y, row in enumerate(L):
|
||
|
|
for x, v in enumerate(row):
|
||
|
|
if v == 'S':
|
||
|
|
start = (x, y)
|
||
|
|
elif v == 'E':
|
||
|
|
end = (x, y)
|
||
|
|
p1, path = BFS(start, end, G)
|
||
|
|
score, seats = BFS(start, end, G)
|
||
|
|
print(p1, len(path))
|