I'm looking for an algorithm that do the following thing.
Given $n$ the number of rows and columns of a matrix of positive integers.
Given $(x_1,y_1)$ the starting coordinates.
Given $(x_2,y_2)$ the ending coordinates.
and $k$ an integer.
This are some rules of how you can travel through the matrix:
When stepped in some coordinate $(x,y)$ with a given value $w$, you can travel to $(x \pm w,y)$ or any value between this range or $(x ,y \pm w)$ or any value between this range.
Also you can spend the integer $k$ in order to travel a little further in a row or a column. For example with $k=4$ you can travel to $(x ,y + w + 3)$ spending $3$ of your $k$. In this case, now you only have $k=1$ to spend.
The objective here is find the minimum path between $(x_1,y_1)$ and $(x_2,y_2)$.
I already implemented an algorithm that do this in $O(n^3k)$, the problem it's that given the implementation it's very difficult to justify its correctness.
How would you resolve this problem in a way that is easily shown it's correctness?