from sys import stdin from math import lcm def tadd(a, b): return tuple(map(sum, zip(a, b))) def tmul(a, b): return tuple([n*b for n in a]) def tmod(a, b): return tuple([a%b for (a,b) in zip(a, b)]) # 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(): cur = {(start, 0, 0)} frontier = set() visited = set(cur) while True: for bv, t, gid in cur: vs = [bv] for d in range(4): vs.append(tadd(bv, tdir(d))) for v in vs: if not coll(*v, t+1): new = None if v == end and gid == 0: new = (v, t+1, 1) elif v == start and gid == 1: new = (v, t+1, 2) elif v == end and gid == 2: return t+1 else: new = (v, t+1, gid) chk = (new[0], new[1] % cycle, new[2]) if not chk in visited: visited.add(chk) frontier.add(new) cur = frontier frontier = set() return None print(search())