DWITE Online Computer Programming Contest, November 2002, Problem 4
A local radio station, COOL-FM (that's Cool with a "C"), recently awarded a lucky listener, the prize of walking through a giant sized chessboard with money prizes at each of the squares on the chessboard. The lucky listener, had to start at the lower left corner and move to the upper right corner, by taking steps either to the right or above (moving to the left, down or on a diagonal was not allowed). The lucky listener claimed each of the money prizes at each of the squares they stepped on.
Your job is to find the five best routes through the chessboard yielding the most money for the lucky listener.
Input Specification
The first line of the input will consist of an integer , the size
of the chessboard. Each subsequent line represents one row on the
chessboard. Each line will contain
integers for the locations on the
chessboard for that row. Each integer
represents the amount of money
at that location,
. These integers will be separated by a
single space. The first number in the
line would be the
starting point for the lucky listener. The
number in the
first line would be the ending point.
Output Specification
The output will contain five lines of data, each representing the amount of money (as an integer) that would be obtained on the five best routes, from best to fifth best. It is possible to have different routes with the same amount.
Grading
The test data will have partial marks! One test case has , but the other has
.
Sample Input
8
4 3 1 0 0 5 12 10
5 3 12 0 0 1 4 3
1 10 3 0 0 2 12 3
4 4 4 4 4 4 0 0
3 1 12 0 0 25 2 0
0 4 5 7 7 7 4 5
4 6 9 1 0 0 0 12
12 2 1 6 0 0 1 2
Sample Output
126
124
124
122
122
Comments