Solving the math puzzle of the Schönbrunn maze in Vienna

	5 5
	4 2
	2 2
	2 -2 4 -1 3
	-3 3 -1 3 -2
	1 -2 0 -2 3
	-3 2 -3 2 -4
	4 -2 1 -3 2

	# read the input from a file
	n, m = [int(c) for c in input().split(' ')]
	sx, sy = [int(c) for c in input().split(' ')]
	ex, ey = [int(c) for c in input().split(' ')]

	# utilities to convert coordinates to vertex id and vice versa
	def coord_to_id(i, j):
	return i * m + j

	def id_to_coord(x):
	return (x // m, x % n)

	# store the grid
	g = [ [int(c) for c in input().split(' ')] for _ in range(n)]

	# build the graph
	graph = {}
	for i in range(n):
	for j in range(m):
	# read how many steps can be taken
	steps = abs(g[i][j])
	if steps == 0:
	continue
	x = coord_to_id(i, j)
	# define the list of neighbors
	graph[x] = []
	# from the current tile x, jump "steps" tile up, left, down, right
	if i - steps >= 0:
	graph[x].append(coord_to_id(i-steps, j))
	if i + steps < n:
	graph[x].append(coord_to_id(i+steps, j))
	if j - steps >= 0:
	graph[x].append(coord_to_id(i, j-steps))
	if j + steps < m:
	graph[x].append(coord_to_id(i, j+steps))

	start = coord_to_id(sx, sy)
	end = coord_to_id(ex, ey)

	# store all the solutions
	paths = []
	# backtrack a solution
	prev = {}
	visited = set()
	prev[start] = None

	# called dfs, but is actually a complete search
	def dfs(u):
	if u == end:
	a = end
	p = []
	while a != None:
	p.append(a)
	a = prev[a]
	paths.append(p)
	return
	for v in graph[u]:
	if v not in visited:
	visited.add(v)
	prev[v] = u
	dfs(v)
	# complete search: pretend this path was not explored
	# to consider it later
	visited.remove(v)

	# search
	visited.add(start)
	dfs(start)

	# results
	solutions = []
	for p in paths:
	tiles = [id_to_coord(tile) for tile in p[::-1]]
	s = sum([g[x[0]][x[1]] for x in tiles])
	# log all the solutions
	solutions.append((s, len(tiles), tiles))

	# find the best
	best = min(solutions, key=lambda s: (abs(s[0]), s[1]))
	print('The best solution is a sum of', best[0], 'in', best[1], 'steps.')
	sol = ' -> '.join([str(c) + ', tile ' + str(g[c[0]][c[1]]) for c in best[2]])
	print(sol)