Graphical Key Graphical Key
Challenging
RU JA English
As soon as the buttons were pressed in the correct order, the floor beneath you swiftly broke apart and you fell into a deeper level of the dungeon. This castle still hasn’t ceased to surprise you! Fortunately, you didn’t hurt yourself during the fall, otherwise you could’ve forget about ever going home.

Standing up and sorting yourself out, you saw a door which looked as if an unimaginable treasure was hidden behind it - massive, metal, and despite the past centuries without a single spot of rust. There were two options - it was either made of stainless steel, or all these years someone carefully looked after it. You would very much like the first option to be true. One encounter with a ghost was quite enough.

This door didn’t have anything even remotely resembling a keyhole. But there was a small field, suspiciously similar to the touch screen with dots. It resembled a lock that requires drawing of a certain pattern to be unlocked. Where could such technologies come from in the old castle?! Hundreds of different ideas raced through your mind, one crazier than the other. But all of this can wait until you are on the way home. The priority now is to open this door.

As soon as you’ve touched the screen, each point turned into a digit. Probably, you need to draw some kind of an unlock pattern here. Except… On what principle to choose the digits?

Your task is to write a function that accepts a set of digits (a two-dimensional array) as an argument, and then returns the sum of the digits on the direction from the upper-left corner to the lower right so that the sum is maximum. At the same time, you can visit no more than N points, taking into account the first and the last one. You can move in any of the 8 directions (horizontally, vertically and diagonally).

Input: array of numbers, length of the path.

Output: the sum of the numbers on the path.

Example:

g_key([[1, 6, 7, 2, 4],
       [0, 4, 9, 5, 3],
       [7, 2, 5, 1, 4],
       [3, 3, 2, 2, 9],
       [2, 6, 1, 4, 0]], 9) == 46

How it is used: For the pathfinding.

Precondition:
2x2 <= grid size <= 5x5