1998 Canadian Computing Competition, Stage 1

Problem E: Mountain Passage

Alp the mountain climber is on the northwest corner of a square area of a mountainous terrain and wishes to find a passage to the opposite (southeast) corner. Alp is currently at an elevation at which oxygen is not needed, but at any higher elevation oxygen is required. Oxygen, when required, is used at the rate of one unit per horizontal step.

The northwest corner of the terrain is at position (1, 1) and the southeast corner is at position (n, n), where n is a positive integer read from the input file. The elevation of each point (x, y), (1 ≤ x, y ≤ n), is an integer read from the input; each elevation occupies a single line in the input file.

Alp moves in a series of horizontal steps, where each step moves Alp a unit north, a unit south, a unit east, or a unit west. Alp must remain in the square region and cannot climb or descend more than 2 units of elevation in a single step. If the elevation at either the beginning or the end of the step requires oxygen, a unit of oxygen is consumed by Alp during the step.

Input

The first line of input is a positive integer indicating the number of trips that Alp must make. For each trip there is a number of input lines. The first line for each trip contains an integer n ≤ 25, indicating the size of the square area of terrain. The next n² lines each contain a single integer indicating the elevation of a particular point of terrain. The elevations are given for the points in the following order: (1, 1), (1, 2), (1, 3), .. (1, n), (2, 1), (2, 2), ... (n, 1), (n, 2), .. (n, n).

Output

For each trip, if a passage exists, the output is a single line containing an integer indicating the number of units of oxygen consumed. If a passage does not exist, the output is a single line containing the message "CANNOT MAKE THE TRIP". Output lines for the trips should be separated by a single blank line.

Sample Input

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

Sample Output

5
 
CANNOT MAKE THE TRIP

All Submissions
Best Solutions

Point Value: 10
Time Limit: 2.00s
Memory Limit: 16M
Added: Sep 27, 2008

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

Is there a constraint on the elevation values?

Assume the elevation can fit in a standard integer type.

It says "1997 Canadian Computing Competition, Stage 1" for some reason even though problem is 1998.

right,down,right,down,left,down,down,right,right,right.
5->4->5->6->8->8->6->5->4->5->3

Only the 6,8,8,6 use oxygen, = 4

[quote]If the elevation at either the beginning or the end of the step requires oxygen, a unit of oxygen is consumed by Alp during the step.[/quote]

A unit of oxygen is consumed when moving to 6, then another to 8, then another to 8, then another to 8, then another to 5.

If there is a passage, are we supposed to output the least amount of oxygen consumed possible?

Yes.

"For each trip, if a passage exists, the output is a single line containing an integer indicating the number of units of oxygen consumed. If a passage does not exist, the output is a single line containing the message "CANNOT MAKE THE TRIP". Output lines for the trips should be separated by a single blank line."

I don't think this is a DP problem; none of the solutions are dynamic (Jacob calls his "recursive-dynamic", but it's not dynamic in the true sense of the term). I think it should be removed from the Dynamic Programming category.

Recursive-dynamic is a subset of Dynamic.

This problem is Recursive-dynamic.

Therefore, this problem is Dynamic.

QED

If it can't be done bottom-up, then it's not dynamic. Evidently recursive-dynamic is not a subset of dynamic.

Edit: anyways, Hanson told me how to remove it, so it's done.

so the oxygen needed is solely depedent on the starting elevation?

oxygen is required every step you take, as long as it is valid (i.e. elevation is within 2).

Say you're going from an elevation of 6 to 3. I'd assume that's not valid right?

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

the answer is 5.

can someone tell me which path to take that uses 5 oxygen?

down, down, right, down, down, right, right, right
5, 7, 8, 8, 6, 5, 4, 5, 3
The steps 5->7, 7->8, 8->8, 8->6, and 6->5 require oxygen.

yes, 6 to 3 is invalid.