95 lines
2.2 KiB
Python
Executable File
95 lines
2.2 KiB
Python
Executable File
#!/usr/bin/env python3
|
|
|
|
from numba import jit
|
|
from useful import *
|
|
|
|
target = 64 if not len(sys.argv) > 1 else int(sys.argv[1])
|
|
|
|
DIRS = (-1, 0), (1, 0), (0, -1), (0, 1)
|
|
|
|
def add(a, b):
|
|
return tuple(map(lambda u, v: u + v, a, b))
|
|
|
|
def cango(pos):
|
|
global w, h
|
|
return pos[0] >= 0 and pos[1] >= 0 and pos[0] < h and pos[1] < w and \
|
|
kart[pos] != '#'
|
|
|
|
@jit
|
|
def cango2(pos):
|
|
global w, h
|
|
u, v = 0, 0
|
|
rpos = [*pos]
|
|
if pos[0] < 0:
|
|
u = -1
|
|
rpos[0] = h - 1
|
|
elif pos[1] < 0:
|
|
v = -1
|
|
rpos[1] = w - 1
|
|
elif pos[0] >= h:
|
|
u = 1
|
|
rpos[0] = 0
|
|
elif pos[1] >= w:
|
|
v = 1
|
|
rpos[1] = 0
|
|
return u, v, tuple(rpos), kart[tuple(rpos)] != '#'
|
|
|
|
def solve(kart, pos, dist):
|
|
global dmap, target, q
|
|
if dist > target:
|
|
return
|
|
if dist >= dmap[pos]:
|
|
return
|
|
dmap[pos] = dist
|
|
for d in DIRS:
|
|
nextpos = add(pos, d)
|
|
if cango(nextpos):
|
|
q += [(kart, nextpos, dist + 1), ]
|
|
|
|
def solve2(kart, pos, dist, os, oe):
|
|
global dmap2, target, q
|
|
if dist > target:
|
|
return
|
|
if dist >= dmap2[pos][os][oe] and win(dmap2[pos][os][oe]):
|
|
return
|
|
dmap2[pos][os][oe] = dist
|
|
for d in DIRS:
|
|
nextpos = add(pos, d)
|
|
u, v, realpos, ok = cango2(nextpos)
|
|
if ok:
|
|
q += [(kart, realpos, dist + 1, os + u, oe + v), ]
|
|
|
|
def win(x):
|
|
return x % 2 == target % 2
|
|
|
|
def vectorable(x):
|
|
acc = 0
|
|
for sk in x:
|
|
for ek in x[sk]:
|
|
if win(x[sk][ek]):
|
|
acc += 1
|
|
return acc
|
|
|
|
kart = np.asarray([[c for c in l] for l in lines(open(0))])
|
|
h, w = kart.shape
|
|
dmap = np.ones((h, w), dtype=int) * 26501366
|
|
beg = next(zip(*np.where(kart == 'S')))
|
|
q = deque()
|
|
|
|
q += [(kart, beg, 0)]
|
|
|
|
while q:
|
|
solve(*q.popleft())
|
|
|
|
print(np.sum(np.vectorize(lambda x: x <= target and x % 2 == 0)(dmap)))
|
|
|
|
dmap2 = np.zeros((h, w), dtype=dict)
|
|
# {offset (# of maps) south: {offset east: best}}
|
|
for (u, v), _ in np.ndenumerate(dmap2):
|
|
dmap2[u,v] = defaultdict(lambda: defaultdict(lambda: 666))
|
|
q += [(kart, beg, 0, 0, 0)]
|
|
while q:
|
|
#ic(dmap2[2, 2][2][2])
|
|
solve2(*q.popleft())
|
|
print(np.sum(np.vectorize(vectorable)(dmap2)))
|