93 lines
2.3 KiB
Python
Executable File
93 lines
2.3 KiB
Python
Executable File
#!/usr/bin/env python3
|
|
|
|
from useful import *
|
|
|
|
DIRS = (-1, 0), (1, 0), (0, -1), (0, 1)
|
|
UP, DOWN, LEFT, RIGHT = DIRS
|
|
MUSTGO = {'<': LEFT, '>': RIGHT, '^': UP, 'v': DOWN}
|
|
|
|
def add(a, b):
|
|
return tuple(map(lambda u, v: u + v, a, b))
|
|
|
|
def cango(here, step):
|
|
return kart[here] == '.' or step == MUSTGO[kart[here]]
|
|
|
|
def solve(kart, pos, dist):
|
|
global best, q
|
|
if pos == fin:
|
|
best = dist
|
|
return
|
|
if not (pos[0] >= 0 and pos[1] >= 0 and pos[0] < h and pos[1] < w):
|
|
return
|
|
if not kart[pos]:
|
|
return
|
|
newkart = kart.copy()
|
|
newkart[pos] = False
|
|
for d in DIRS:
|
|
if cango(pos, d):
|
|
nextpos = add(pos, d)
|
|
q += [(newkart, nextpos, dist + 1), ]
|
|
|
|
kart = np.asarray([[c for c in l] for l in lines(open(0))])
|
|
h, w = kart.shape
|
|
beg, fin = [(i, np.argmax(kart[i] == '.')) for i in (0, h - 1)]
|
|
q = deque()
|
|
best = 0
|
|
longest100 = 0
|
|
|
|
q += [(kart != '#', beg, 0)]
|
|
|
|
while q:
|
|
solve(*q.popleft())
|
|
|
|
print(best)
|
|
|
|
vertices = [beg, fin]
|
|
edges = defaultdict(lambda: set())
|
|
|
|
def find_vertices(kart, pos, dist, prev_vertex):
|
|
global vertices, edges, q
|
|
newkart = kart.copy()
|
|
newkart[pos] = False
|
|
newposes = []
|
|
for d in DIRS:
|
|
nextpos = add(pos, d)
|
|
if not (nextpos[0] >= 0 and nextpos[1] >= 0 and nextpos[0] < h and nextpos[1] < w):
|
|
continue
|
|
if not kart[nextpos]:
|
|
continue
|
|
newposes += [nextpos, ]
|
|
if len(newposes) > 1: # we're on a new(?) vertex
|
|
if pos not in vertices:
|
|
vertices += [pos, ]
|
|
for p in newposes:
|
|
q += [(newkart, p, 1, pos), ]
|
|
edges[prev_vertex] |= {(pos, dist)}
|
|
edges[pos] |= {(prev_vertex, dist)}
|
|
elif len(newposes) == 1:
|
|
q += [(newkart, newposes[0], dist + 1, prev_vertex), ]
|
|
elif pos == fin:
|
|
edges[prev_vertex] |= {(pos, dist)}
|
|
edges[pos] |= {(prev_vertex, dist)}
|
|
|
|
def lengths(fro, edges, to):
|
|
if fro == to:
|
|
return [0, ]
|
|
acc = []
|
|
for e in edges[fro]:
|
|
newegg = deepcopy(edges)
|
|
newegg[e[0]].remove((fro, e[1]))
|
|
newegg[fro].remove(e)
|
|
for l in lengths(e[0], newegg, fin):
|
|
acc += [e[1] + l, ]
|
|
return acc
|
|
|
|
q += [(kart != '#', beg, 0, beg), ]
|
|
while q:
|
|
find_vertices(*q.popleft())
|
|
|
|
ic(edges)
|
|
|
|
print(max(lengths(beg, edges, fin)))
|
|
|