Road Rally

Consider a race track laid out on a rectangular grid.

A lowercase x or an uppercase X marks a wall or barrier. Each numeric digit marks a checkpoint. A motorcycle starts on checkpoint 0 and must visit every numbered checkpoint in increasing order, finishing the course on the highest-numbered checkpoint.

The motorcycle moves under momentum, as follows. During the first second it must move to one of the 8 cells neighbouring its starting cell. During every second after that, let $P$ be the cell reached by repeating the exact horizontal and vertical displacement of the previous move; the motorcycle may then move to $P$ or to any of the 8 cells neighbouring $P$. In other words, each component of the velocity may change by at most 1 per second. The motorcycle may never land outside the grid or on an x/X, but it may leap over one or more walls as long as it lands on an empty cell or a checkpoint.

For example, on the layout above the rider might follow the sequence of cells labelled a, b, c, …

reaching the first checkpoint in 6 seconds.

Write a program that finds the shortest time needed to start on 0 and finish on the last checkpoint, landing on each intermediate checkpoint in the order given by the digits. The motorcycle may pass over a checkpoint out of order on its way elsewhere, but it is only credited with visiting that checkpoint once it has already visited every lower-numbered checkpoint.

The input contains several race courses. Each course begins with a line containing two integers $w$ and $h$, the width and the height of the track, with $1 \le w \le 40$ and $1 \le h \le 40$. A line containing 0 0 marks the end of the input.

The header line is followed by $h$ lines of exactly $w$ characters each, describing the track as explained above. Every track has an area of at least 2 and contains at least two checkpoints (0 and 1) and at most 10 checkpoints. When more than two checkpoints are present, they are numbered in a strict, gap-free sequence.

For each course, print on its own line a single integer: the minimum number of seconds needed to complete the course. If the course cannot be completed, print -1 instead.