from sys import stdin from math import lcm from heapq import heappop, heappush def tadd(a, b): return (a[0] + b[0], a[1] + b[1]) # return tuple(map(sum, zip(a, b))) def tmul(a, b): return (a[0] * b, a[1] * b) # return tuple([n*b for n in a]) def tmod(a, b): return (a[0] % b[0], a[1] % b[1]) # return tuple([a%b for (a,b) in zip(a, b)]) def tdist(a, b): return abs(a[0] - b[0]) + abs(a[1] - b[1]) # direction tuple def tdir(f): return ([0, 1, 0, -1][f%4], [-1, 0, 1, 0][f%4]) data = stdin.readlines() start = (data[0].index('.') - 1, -1) end = (data[-1].index('.') - 1, len(data) - 2) data = [l.strip()[1:-1] for l in data[1:-1]] w = len(data[0]) h = len(data) cycle = lcm(w, h) # 0 N 1 E 2 S 3 W blizzards = [set() for _ in range(4)] for y, line in enumerate(data): for x, c in enumerate(line): dirs = "^>v<" if c in dirs: blizzards[dirs.index(c)].add((x, y)) def coll(x, y, t): if (x, y) == start: return False if (x, y) == end: return False if not 0 <= x < w: return True if not 0 <= y < h: return True for d in range(4): v = tmod(tadd((x, y), tmul(tdir(d), -t)), (w, h)) if v in blizzards[d]: return True return False def search(): partOne = None cur = [(0, (start, 0, 0))] visited = set(cur[0][1]) asdf = 0 gid_bonus = tdist(start, end) def dist(node): bv, t, gid = node goal = end if gid != 1 else start score = 0 score += tdist(bv, goal) score += t score -= gid * gid_bonus while True: _, node = heappop(cur) bv, t, gid = node vs = [bv] for d in range(4): vs.append(tadd(bv, tdir(d))) for v in vs: if not coll(*v, t+1): node = None if v == end and gid == 0: if not partOne: partOne = t+1 node = (v, t+1, 1) elif v == start and gid == 1: node = (v, t+1, 2) elif v == end and gid == 2: return partOne, t+1 else: node = (v, t+1, gid) chk = (node[0], node[1], node[2]) if not chk in visited: visited.add(chk) heappush(cur, (asdf, node)) asdf += 1 return None print(search())