Mountain Walking (mtwalk.X)
Farmer Ran and Bessie the cow have embarked on a particularly 'active'
vacation. They spend entire days walking in the mountains and then,
at the end of the day, they tire and return to their vacation cabin.
Since climbing requires a lot of energy and they are already tired,
they wish to return to the cabin using a path that has the smallest
difference between its highest and lowest elevations, no matter how
long that path is. Help FR find this easy-to-traverse path.
The map of the mountains is given by an N x N (2 <= N <= 100) matrix
of integer elevations (0 <= elevation <= 250) FJ and Bessie are
currently at the upper left position (row 1, column 1) and the cabin
is at the lower right (row N, column N). They can travel right, left,
toward the top, or toward the bottom of the grid. They can not travel
on a diagonal.
PROBLEM NAME: mtwalk
INPUT FORMAT:
* Line 1: A single integer: N
* Lines 2..N+1: Line i+1 N space-separated integers describing the
elevations of row i. The first number on the line corresponds
to the first (left) column of the grid, and so on.
SAMPLE INPUT:
5
1 1 3 6 8
1 2 2 5 5
4 4 0 3 3
8 0 2 3 4
4 3 0 2 1
OUTPUT FORMAT:
* Line 1: An integer that is the minimal height difference on the
optimal path.
SAMPLE OUTPUT (file mtwalk.out):
2
OUTPUT DETAILS:
xx... Taking the path shown here, the minimum height is 0 and the
.xx.. maximum is 2, so the difference is 2.
..x..
..x..