Terror on in-line skates

If you take up inline skating you may find going downhill rather
terrifying. When you move to a new town it is helpful to calculate
routes that avoid steep hills. For this problem we consider towns that
are laid out on a rectangular grid with streets running north-south and
east-west. Sample input for two towns is shown below (5 lines).

acabab
bcdefg
dcbabb

a

The first town has 3 e-w streets and 6 n-s streets. There are 18
intersections. The elevation of each intersection is the numerical value
of the character used to label it. For example, intersection g is 5
units higher than the intersections labelled b immediately north and
south of g (indicating steep hills skaters would try to avoid).

The steepness of a hill between two adjacent intersections labelled
x and y is defined as |x-y|.

Given two intersections we look for a route between them which has the
least steep hills. For example to get from g to b immediately south of
it we would travel west to c and then turn south and then go east. This
route avoids any hills with a steepness greater than 1.

When you move to a new town you want to plan routes which allow you to
get from any intersection to any other avoiding steep hills where
possible. In the sample output shown below (7 lines) there is a ' ' or 
'*' between each pair of intersections. A '*' indicates that you will
not use the direct route between those two intersections. There should be
as many '*'s as possible and the total steepness avoided should be as
large as possible.

a*c a b a b
    * * * *
b c d e f g
*   * * * *
d c*b a b b

a

The second town has only one intersection so the output has no ' ' or
'*' for it.

The input used to test your program will consist of one or more town
descriptions separated by blank lines. Each town description has one
n >= 1  lines each containing the same number of characters m >= 1
followed by a '\n'. m will be at most 26. The output for that town will 
have 2n-1 lines each with 2m-1 characters and a '\n'. On the "inbetween" 
lines the ' ' or '*' are separated by ' 's.

The output has the same as the input but with a ' ' or '*' between
each pair of adjacent intersections in each town.

Note that there may be more than one correct output for a town.

The sample input shown above is available for testing as file C.in, 
however, your program must read from stdin/System.in/cin.
File C.in needs to be copied to the directory with your solution.
Use it for testing using input redirection and when you submit your
program the system will run your program with System.in/stdin/cin
connected to the judge's version of the file.