CCC '98 S5 - Mountain Passage

View as PDF
Submit solution
Points: 10
Time limit: 1.0s
Memory limit: 256M
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


  • 1
    maxcruickshanks  commented on Dec. 19, 2022, 3:35 a.m.

    Since the checker was not implemented properly, it was fixed, and all submissions were rejudged.


  • 0
    dxke02  commented on Aug. 19, 2021, 6:47 p.m.

    Since the original data were weak, new data were added to prevent incorrect solutions from passing.


  • 3
    noYou  commented on July 21, 2020, 6:06 p.m. ← edit 2

    I've coded a program to solve the problem, but I don't understand the sample data

    0 0 0 0 0 
1 0 1 2 3 
2 3 2 3 4 
3 4 3 4 5 
4 4 4 4 4

0 0 0 0 0 
1 0 1 2 3 
2 3 2 3 4 
3 4 3 4 5 
3 3 3 3 3 

4  9 
9  4 

0 -1 
-1 -1

    for each test case, the upper and lower blocks represent the data itself and the minimum oxygen requirement respectively. Since this looks fine to me, but is clearly WA for the sample case itself, what did I misunderstand?

    EDIT: Apparently, descending from an elevation that requires oxygen also requires oxygen. The above code is wrong because it assumes the path

    5 > 7 > 8 > 8 > 6 > 5 > 4 > 5 > 3

    should only cost 4, when it is in fact 5.


    • 2
      Evanhyd  commented on Jan. 20, 2021, 5:48 p.m.

      1 oxygen is consumed if the current elevation or the next elevation is above the beginning elevation:

      For example, if Ala starts at [0][0] with an elevation of 5, then any activities (whether it is going up or down) less or equal to that elevation does not need any oxygen (5 -> 4, 4 -> 5, 3 -> 1 etc). If either the activities are above the starting elevation (5 -> 6, 6 -> 5, 4 -> 6, 6 -> 4, 6 -> 8), then it requires 1 oxygen.

      in this case here, the route will be:

      5 > 7 > 8 > 8 > 6 > 5 > 4 > 5 > 3 5-7 requires oxygen, 7-8 requires oxygen, 8-8 requires oxygen, 8-6 requires oxygen, and 6-5 requires oxygen

      Thanks to maxcruickshanks's clarification.


  • 7
    op8  commented on July 2, 2020, 8:41 p.m.

    this question has screwed with my mental health for way too long - for anyone else who may need it: yes, you do need to find the minimum amount of oxygen per trip, it IS NOT guaranteed that there's at most 1 way to get from NW to SE.


  • -2
    Roronoa_Zoro1540  commented on Dec. 11, 2018, 12:18 a.m.

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


    • -13
      JustinXu  commented on Jan. 1, 2019, 8:35 p.m. ← edited

      This comment is hidden due to too much negative feedback. Show it anyway.