Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
depth-first search solution in Clear category for Graphical Key by David_Jones
from collections import defaultdict
def g_key(grid, L):
def DFS(start, end, path, routes, L):
path.append(start)
n = len(path)
if n < L:
for point in neighbors[start]:
if point not in visited:
visited.add(point)
DFS(point, end, path, routes, L)
visited.remove(point)
elif n == L and start == end:
routes.append(path[:])
path.pop()
n = len(grid)
if L == n * n:
return sum(sum(row) for row in grid)
visited = {(0,0)}
neighbors = defaultdict(set)
for i in range(n):
for j in range(n):
for x,y in ((i-1,j-1), (i-1,j), (i-1,j+1), (i,j-1),
(i,j+1), (i+1,j-1), (i+1,j), (i+1,j+1)):
if 0 <= x < n and 0 <= y < n:
neighbors[(i,j)].add((x,y))
routes = []
DFS((0,0), (n-1,n-1), [], routes, L)
return max(sum(grid[i][j] for i,j in route) for route in routes)
May 9, 2019