This is one of the problems that would be reasonably easy... if only the constraints were a bit
smaller. That would allow us to search the entire state space conveniently: we could use BFS to
mark where and with what amount of energy we can be. If we are starting with K energy on an N*N
grid, this solution would run in O(N^2 * K).

To improve this solution, we need to make some observations. First of all, let's look at the 
problem backwards: we start at the goal with 0 energy, we can either increment our current energy
or jump, and for each cell we want to compute the least amount of energy that allows us to reach it.

Now that we did that, we can make an important observation. Suppose that I just found a way to 
reach a cell (x,y) by jumping upwards (decreasing y) with 3 energy. If I, in the future, reach
the same cell by jumping upwards with more than 3 energy, I can immediately discard that branch
of search: whatever I could do next, I can do now.

Thus, for each cell and each direction of arrival we are only interested in the smallest amount
of energy that will allow us to get there. This decreases the number of states to 4*N*N, but
introduces a new problem: now we have too many outgoing edges from each state! Before, we could
do with just 5 (jump up, down, left, right, or decrease energy). Now, it seems we need to consider
jumping in each direction with either the current or any larger amount of energy. How to deal with
that?

Note that we actually did use the same trick in the first, trivial solution. In that solution,
if we wanted to decrease our energy, we did not consider all possible new energies. Instead,
we just considered decreasing our energy by 1 (knowing that from *that* state we will consider
another decrease, and so on). Only now the implementation will be a bit tricky. Here's the essence:
suppose I just made a jump upwards with 3 energy. After the jump, I'll get the chance to extend 
it and actually jump with 4 energy. (And from *that* state I'll get the chance to extend it 
even more to a jump with 5 energy, and so on.)

Here's a neat way to implement the above solution in O(N^2): We will have 5*N^2 states: for 
each cell, there will be five: "I'm here", "I just arrived by jumping upwards", and
the same for other four directions. For a cell (x,y) we will denote these states (x,y,0),
(x,y,U), (x,y,D), (x,y,L), and (x,y,R).

On these states, we will incrementally build a graph with length-0 and length-1 edges such
that the shortest distance from the starting state (goal_x,goal_y,0) to any state (x,y,0)
will be the minimum energy with which said cell is reachable.

We'll start by placing the state (goal_x,goal_y,0) into the queue (remembering that the minimum 
energy for (goal_x,goal_y) is zero). Each time we process a state (x,y,0) with minimum energy
d, we get four outgoing edges: into (x,y-d,U), and similarly for the other three directions.
Each of these edges has length 0. (It does not change our energy.) From (x,y-d,U) we can go 
either to (x,y-d,0) with length 0, or we can go to (x,y-d-1,U) with length 1. (This corresponds
to incrementing our energy *before* making the previous jump.) Obviously, we do the same thing
for the other three directions, and that's it.