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) - 3) 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 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)} frontier = set() while True: for bv, t 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): if v == end: return t+1 frontier.add((v, t+1)) cur = frontier frontier = set() return None print(search() + 1)