```# A simple recursive solution, not very efficient.
# One could use dynamic programming, similar to what I used in

@maze = [
[ 1, 3, 0, 5,-1, 7,-1,-1, 0, 4, 2, 1],
[-1, 3, 2, 1,-1, 4,-1, 5, 3,-1, 1, 0],
[ 5, 4, 8,-1, 3, 2, 2,-1, 4,-1, 0, 0],
[ 2, 1, 0, 4, 1,-1, 8, 0, 2,-1, 2, 5],
[ 1, 4, 0, 1,-1, 0, 3, 2, 2, 4, 1, 4],
[ 0, 1, 4, 1, 1, 6, 1, 4, 5, 2, 1, 0],
[ 3, 2, 5, 2, 0, 7,-1, 2, 1, 0,-1, 3],
[ 0,-1, 4,-1,-1, 3, 5, 1, 4, 2, 1, 2],
[ 5, 4, 8,-1, 3, 2, 2,-1, 4,-1, 0, 0],
[ 2, 1, 0, 4, 1,-1, 8, 0, 2,-1, 2, 5],
[ 1, 3, 0, 5,-1, 7,-1,-1, 0, 4, 2, 1],
[ 0, 0, 3, 1, 5, 2, 1, 5, 4, 1, 3, 3],
]
def @maze.max_x; size - 1; end
def @maze.max_y; map { |x| x.size - 1 }.min; end

def traceback(x, y, steps, score)
if x == 0 && y == 0
[score+@maze[x][y], steps+[[x,y]]]
elsif x < 0 || y < 0 || @maze[x][y] < 0
[-1, steps]
else
[traceback(x-1, y, steps+[[x,y]], score+@maze[x][y]),
traceback(x, y-1, steps+[[x,y]], score+@maze[x][y])
].max
end
end

score, steps = traceback(@maze.max_x, @maze.max_y, [], 0)

0.upto(@maze.max_x) { |x|
0.upto(@maze.max_y) { |y|
print steps.include?([x, y]) ? "[#{@maze[x][y]}]" : ("%2d " % @maze[x][y])
}
puts
}

--
Christian Neukirchen  <chneukirchen / gmail.com>  http://chneukirchen.org

```