CCC '98 S5 - Mountain Passage

View as PDF

Submit solution

Points: 10
Time limit: 2.0s
Memory limit: 16M

Problem type

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 \le x, y \le 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 Specification

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 \le 25, indicating the size of the square area of terrain. The next n^2 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), \dots (1, n), (2, 1), (2, 2), \dots (n, 1), (n, 2), \dots (n, n).

Output Specification

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

Comments


  • -4
    Roronoa_Zoro1540  commented on Dec. 10, 2018, 7:18 p.m.

    do you have to find the minimum amount of oxygen for each trip?


    • 0
      JustinXu  commented on Jan. 1, 2019, 3:35 p.m. edited

      There will be only one way at maximum to get from the northwest to the southeast.


    • 0
      JustinXu  commented on Jan. 1, 2019, 3:34 p.m. edited

      Why is there only 1 test case?!?!?!?!?!

      (EDIT: This was not meant to be a reply)


  • 2
    aeternalis1  commented on July 19, 2017, 1:00 p.m.

    Invalid return

    Why does my submission get an invalid return? I set the recursion limit to 625*T(number of trips), which should be the max amount of recursions necessary in the problem.