57 lines
1.6 KiB
Python
Executable File
57 lines
1.6 KiB
Python
Executable File
#!/usr/bin/env python3
|
|
from useful import *
|
|
|
|
a = np.asarray([[ord(c) for c in l] for l in lines(open(0))])
|
|
#a = np.arange(9).reshape((3,3)) # todo remove
|
|
E, S = (0,0), (2,2)
|
|
for (y, x), v in np.ndenumerate(a): # bleh
|
|
if v == ord('S'):
|
|
S = (y, x)
|
|
a[y,x] = ord('a')
|
|
elif v == ord('E'):
|
|
E = (y, x)
|
|
a[y,x] = ord('z')
|
|
h, w = a.shape
|
|
ic(w,h)
|
|
ic(a[18:23,:5])
|
|
p = np.pad(a, 1, mode='edge')
|
|
goto = [[p[u:h+u,v:w+v] - a <= 1 for v in range(3)] for u in range(3)]
|
|
#ic(goto)
|
|
s = np.empty((h, w))
|
|
s.fill(h*w) # enough
|
|
tovisit = deque([S])
|
|
def visits(y, x):
|
|
return [(y+u-1, x+v-1) for (u, v) in [(2, 1), (0, 1), (1, 2), (1, 0)]
|
|
if y+u-1 >= 0 and y+u-1 < h and x+v-1 >= 0 and x+v-1 < w
|
|
and goto[u][v][y,x]]
|
|
done = False
|
|
for i in range(h*w): # still enough
|
|
if done: break # gah
|
|
lenv = len(tovisit)
|
|
for j in range(lenv):
|
|
here = tovisit.popleft()
|
|
if here[0] == E[0] and here[1] == E[1]: # ugh
|
|
print(i)
|
|
done = True
|
|
break
|
|
if s[here[0],here[1]] > i:
|
|
s[here[0],here[1]] = i
|
|
tovisit.extend(visits(*here))
|
|
|
|
s.fill(h*w)
|
|
goto = [[p[u:h+u,v:w+v] - a >= -1 for v in range(3)] for u in range(3)]
|
|
tovisit = deque([E])
|
|
done = False
|
|
for i in range(h*w):
|
|
if done: break
|
|
lenv = len(tovisit)
|
|
for j in range(lenv):
|
|
here = tovisit.popleft()
|
|
if a[here[0],here[1]] == ord('a'):
|
|
print(i)
|
|
done = True
|
|
break
|
|
if s[here[0],here[1]] > i:
|
|
s[here[0],here[1]] = i
|
|
tovisit.extend(visits(*here))
|