import sys input = sys.stdin map = [] for line in input: map.append(list(line.strip())) # construct a graph for i,c in enumerate(map[0]): if c == '.': start = (i,0) break def neighbors(x,y): n = [] c = map[y][x] for i,j in [(y-1,x),(y+1,x),(y,x-1),(y,x+1)]: if 0 <= i < len(map) and 0 <= j < len(map[i]): if map[i][j] != '#': n.append((j,i)) return n spots = [] for i in range(len(map)): for j in range(len(map[i])): if map[i][j] in '.<>v^': n = neighbors(j,i) if len(n) not in (0,2): spots.append((j,i)) def reachable(start,spots): q = [(0,start)] dist = {} r = [] while q: q.sort() n,(x,y) = q.pop(0) if (x,y) in dist: continue #print(x,y,neighbors(x,y)) if (x,y) in spots and (x,y) != start: r.append((n,(x,y))) else: dist[x,y] = n for j,i in neighbors(x,y): if (j,i) not in dist: q.append((n+1,(j,i))) return r G = {} for p in spots: G[p] = reachable(p,spots) from pprint import pprint pprint(G) for p in G: if p[1] == len(map)-1: goal = p print("start=",start) print("goal=",goal) print("brute force...") def longest(p, seen, depth): best = -10000000 b = [] if p == goal: return 0,[] if p in seen: raise Error("alredy seen") seen.add(p) for n,q in G[p]: if q not in seen: t,path = longest(q, seen, depth+1) if t+n > best: best = t+n b = [q]+path seen.remove(p) return best, b print(longest(start,set(),0))