My 8-yr old has gotten bored creating conventional mazes, and has taken to creating variants that look like this:
The idea is to start from x and reach o via the normal rules. Additionally, you can "hop" from any integer $a$ to any other integer $b$, but you must pay $|a-b|$ dollars for the privilege. The goal is to solve the maze for the least cost. In the example above, we could go from x to o via x-14-18-27-28-o at cost 5, but it's cheaper to go x-13-11-9-8-29-28-o for only 4.
So here is my question: what is the best solution (in terms of asymptotic running time) you can think of for solving this? You may make any reasonable assumptions about the input format.
Note: I am using the "puzzles" tag here because I have an $O(n^2)$ answer in mind, but I'm not sure it's optimal and would like to see if someone else can improve my solution. (Here $n$ is the number of integers in the maze.)