Hills

Finds the easiest path through hilly terrain

Search for a path through a rectangular grid of heights that minimizes the changes in elevation.

Model

The points in the grid are linked to orthogonal neighbours. The links are costed using the formula

sqrt( 1 + ( height(a) - (height(b) )^2 )

Input

A space delimited text file.

File format

The first line in the input file should be

format hills

Elevation grid

Specifies elevation of an m row and n column grid

Column	Desscription
1	"o", for orthogonal grid
2 ... n+1	height for each location in a row n wide

Starting and ending locations

Column	Desscription
1	"s", for start
2	x location column, 1-based
3	y location row, 1-based

Column	Desscription
1	"e", for end
2	x location column, 1-based
3	y location row, 1-based

Sample input

format hills
o 1 2 3
o 2 5 2
o 3 2 1
s 1 1
e 3 3

Algorithm

Dijkstra