Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Express Delivery by tokiojapan55
from typing import List
from math import inf
MOVE = {'D':(1,0),'U':(-1,0),'R':(0,1),'L':(0,-1)}
def get_route(path):
time = 0
route = ''
for n in range(len(path)-1):
r1,c1,b1 = path[n]
r2,c2,b2 = path[n+1]
if r1==r2 and c1==c2:
if b1==b2:
raise Exception()
route += 'B'
time += 1
else:
if b1!=b2:
raise Exception()
for d in MOVE.keys():
if (r1+MOVE[d][0], c1+MOVE[d][1]) == (r2, c2):
route += d
break
time += b1 + 1
return (time,route)
def checkio(field_map: List[str]) -> str:
matrix = [list(m) for m in field_map]
len_r,len_c = len(matrix),len(matrix[0])
min_table = dict()
stack = []
for r in range(len_r):
for c in range(len_c):
min_table[(r,c,0)] = inf
min_table[(r,c,1)] = inf
if matrix[r][c] == 'S':
stack.append([(r,c,1)])
min_table[(r,c,1)] = 0
min_time = inf
result = []
while stack:
path = stack.pop(0)
r,c,b = path[-1]
t = get_route(path)[0]
if b == 1 and matrix[r][c] == 'E':
if t < min_time:
min_time = t
result = path
elif t < min_time:
if matrix[r][c] == 'B':
action = (r,c,1-b)
if action not in path:
if t+1 < min_table[action]:
stack.append(path + [action])
min_table[action] = t+1
for dr,dc in MOVE.values():
if 0<=r+dr
April 20, 2020
