#!/usr/bin/env python3 import sys import heapq from collections import defaultdict def parse(): G = [] for l in sys.stdin: G.append([c for c in l.strip()]) # all examples the same w S at bottom left facing east return G, (len(G) - 2, 1), '>' def pprint(G): for i in range(len(G)): for j in range(len(G[0])): print(G[i][j], end="") print("") def step(pos, dir): i, j = pos if dir == "^": return (i-1, j) elif dir == ">": return (i, j+1) elif dir == "v": return (i+1, j) elif dir == "<": return (i, j-1) else: raise Exception(f"Bad dir: {dir}") # Return [(cost, newpos, newdir)] def neighs(G, pos, dir): if dir == "^" or dir == "v": return [(1, step(pos, dir), dir), (1001, step(pos, ">"), ">"), (1001, step(pos, "<"), "<")] elif dir == ">" or dir == "<": return [(1, step(pos, dir), dir), (1001, step(pos, "^"), "^"), (1001, step(pos, "v"), "v")] else: raise Exception(f"Bad dir: {dir}") def walk(G, pos, dir): h = [] best = 100000 dist = defaultdict(lambda: 100000) tiles = set() heapq.heappush(h, (0, pos, dir, [pos])) while h: (cost, pos, dir, pth) = heapq.heappop(h) #print(cost, pos, dir, pth) if cost > dist[(pos, dir)]: continue dist[(pos, dir)] = cost if G[pos[0]][pos[1]] == "E" and cost <= best: best = cost for p in pth: tiles.add(p) for neigh in neighs(G, pos, dir): (ecost, npos, ndir) = neigh if G[npos[0]][npos[1]] == '#': continue heapq.heappush(h, (cost + ecost, npos, ndir, pth + [npos])) return best, len(tiles) if __name__ == '__main__': G, pos, dir = parse() print(walk(G, pos , dir))