51 lines
1.1 KiB
Python
51 lines
1.1 KiB
Python
|
import sys
|
||
|
|
import networkx as netx
|
||
|
|
|
||
|
|
M = [ list(l) for l in sys.stdin.read().splitlines() ]
|
||
|
|
H = len(M)
|
||
|
|
W = len(M[0])
|
||
|
|
START = tuple()
|
||
|
|
END = tuple()
|
||
|
|
G = netx.DiGraph()
|
||
|
|
|
||
|
|
for x in range(H):
|
||
|
|
for y in range(W):
|
||
|
|
k = (x,y)
|
||
|
|
v = M[x][y]
|
||
|
|
if v == 'S':
|
||
|
|
START = k
|
||
|
|
v = 'a'
|
||
|
|
if v == 'E':
|
||
|
|
END = k
|
||
|
|
v = 'z'
|
||
|
|
v = ord(v)
|
||
|
|
for dx,dy in [(-1,0),(1,0),(0,-1),(0,1)]:
|
||
|
|
nx, ny = (x+dx, y+dy)
|
||
|
|
if nx>=0 and nx<H and ny>=0 and ny<W:
|
||
|
|
nk = (nx,ny)
|
||
|
|
nv = M[nx][ny]
|
||
|
|
if nv == 'S':
|
||
|
|
nv = 'a'
|
||
|
|
if nv == 'E':
|
||
|
|
nv = 'z'
|
||
|
|
nv = ord(nv)
|
||
|
|
dv = nv - v
|
||
|
|
if dv <=1: # can go down !
|
||
|
|
G.add_edge(k,nk)
|
||
|
|
|
||
|
|
print(G)
|
||
|
|
|
||
|
|
# part 1
|
||
|
|
S = netx.shortest_path(G, START, END)
|
||
|
|
print(len(S), "=>", len(S)-1)
|
||
|
|
for (x,y) in S:
|
||
|
|
M[x][y] = "\033[30;43m"+M[x][y].upper()+"\033[0m"
|
||
|
|
print("\n".join("".join(l) for l in M))
|
||
|
|
|
||
|
|
# part 2
|
||
|
|
R = []
|
||
|
|
for x in range(H):
|
||
|
|
S = netx.shortest_path(G, (x,0), END)
|
||
|
|
R.append(len(S)-1)
|
||
|
|
print(min(R))
|