Problem 5:
Shortest path between points in a grid
Given a grid of numbers, and two points in the grid P=(px,py) and Q=(qx,qy),
find the lowest cost path to travel between P and Q using horizontal and vertical
moves. The cost is equal to the sum of the numbers on the squares traversed.
For example, consider the grid below and the points P=(0,3), and Q=(3,3)
0 1 2 3
-----------
0 | 5 4 7 2
1 | 1 1 2 1
2 | 8 4 1 9
3 | 3 5 1 2
The lowest cost path will be the sequence
(0,3), (1,3), (1,2), (2,2), (3,2), (3,3)
With a total cost of 2+1+2+1+1+2 = 9. Compare this to the direct route
going straight down, which has a cost of 2+1+9+2 = 14.
Write a program that will read a grid from stdin as specified below, followed
by two points, and then compute the shortest path and display the shortest path
between two points, and the cost of that path. The grid will be specified as
numRows numColumns
rows
For example, the grid above and starting points would be specified with the input:
4 4
5 4 7 2
1 1 2 1
8 4 1 9
3 5 1 2
0 3
3 3
Given that input, your program should give the output:
Optimal Path cost: 9
Optimal path: (0,3), (1,3), (1,2), (2,2), (3,2), (3,3)
To hand in the program, use the command:
handin acmjudge prog5