2008/2009 SOUTHERN CALIFORNIA REGIONAL
ACM INTERNATIONAL COLLEGIATE PROGRAMMING CONTEST

Problem 2
Rover Obstacles

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.

Sample Input

 3
 5 5 4
 3 9 1
 3 2 7
 5
 3 7 2 0 1
 2 8 0 9 1
 1 2 1 8 1
 9 8 9 2 0
 3 6 5 1 5
 7
 9 0 5 1 1 5 3
 4 1 2 1 6 5 3
 0 7 6 1 6 8 5
 1 1 7 8 3 2 3
 9 4 0 7 6 4 1
 5 8 3 2 4 8 3
 7 4 8 4 8 3 4


Output for the Sample Input

 Problem 1: 20
 Problem 2: 19
 Problem 3: 36



File translated from TEX by TTH, version 3.77.
On 18 Nov 2008, 22:09.