Finding minimum path in a matrix algoritm
A conceptually simple approach is to form an unweighted graph with $(k+1)n^2$ vertices: one copy of the matrix for each possible number of credits remaining.  Each edge represents a way you can travel in a single step.  You start at $(x_1,y_1,k)$ and want to end at $(x_1,y_1,0)$.  Now, look for the shortest path in this graph.  There is a straightforward algorithm to find the shortest unweighted path in such a graph.  Also, any good algorithms textbook will tell you how to justify its correctness.

This should produce an approach where it is very easy to justify its correctness.  Its running time is not the best possible, but it's not too terrible, either.  The running time is something like $O(n^2 k^2 w)$: the degree of each vertex is $O(kw)$, and there are $O(n^2 k)$ vertices, so $O(n^2 k^2 w)$ edges in total.  This is $O(n^3 k^2)$, so not too much slower than your algorithm.  If your primary criterion is ease of justifying correctness, this might be a simple solution.