Your team is assisting with programming for a
robotic rover. To conserve energy, the rover needs to find optimal
paths across rugged terrain to get from a given starting location to
the desired final location. The following model is the first
approximation developed for this problem.
The area to be traversed is modeled as a square grid of cells.
Each cell contains a positive integer from 0 to 9 representing the
energy required to traverse the cell.
Your team is to write a program that will read a series
of N × N square matrices and determine the minimum amount of energy
needed to get from the
top left cell (0,0) to the bottom
right cell (N-1,N-1). Legal moves are up, down, left, and right;
that is, either the row index changes by one or the column index
changes by one, but not both.
Input to your program will be a series of matrices. Each matrix has a
header line containing a single integer between 2 and 125 giving
the number of rows and columns in the N × N square matrix.
Following the matrix size specification are the N matrix rows, each
containing N values. These values will be single integers, 0
through 9, separated by single spaces. The input is
terminated by end-of-file.
For each input matrix,
your program is to print a single line giving the number of the matrix
(starting at one) and the minimum possible cost to get from the top left
to the bottom right corner. Use the format shown in the sample output:
the word "Problem" beginning in the first column, followed by a space,
the problem number, a colon, another space, and the minimum cost. No
trailing whitespace is to appear on an output line.