Number-Hopper Maze

http://cstheory.stackexchange.com/questions/6358/solving-a-number-hopper-mazehttps://cstheory.stackexchange.com/questions/6358/solving-a-number-hopper-maze

Write a program that solves the Number-Hopper maze described above. The input will be an ASCII art description of the maze

+------------+-----+
|x        |18|28  o|
| +--+--+ |  +--+--+
| |13|29|4|27|10|25|
| |  |  +-+--+     |
| |  |       +-----+
| |  |    |      23|
| |  +----+  ------+
| |  |    |        |
| |  | |  +------  |
| |  | |           |
| |  | |  ------+--+
| |  | |        |8 |
| |  | +-----+  |  |
| |  |  22|9 |  |  |
| |  +----+  |  |  |
|       14|11|     |
+---------+--+-----+

• - and + are walls, they are interchangeable
• x is the starting point
• o (lowercase O) is the destination

The numbers are hop points, to hop from number A to B, you must pay the cost of abs(A - B), the positive difference between two numbers. The goal is to find the solution with the minimum cost.

The solution for the example above is x-13-11-9-8-29-28-o, with total cost of 4.

The input of the program will be the ASCII art of the maze, and the output is the sequence of numbers to hop, with the total cost. In the format of x-13-11-9-8-29-28-o 4

To qualify, you algorithm must be under or equal to O(n^2). Include an informal proof if others suspect you.

I don't want to see pure brute-force solutions where obvious bad solutions such as moving in loops and making total 99999-steps for a small maze are included in the solution space.

The shortest code wins.