CCC '98 S5 - Mountain Passage

View as PDF

Submit solution

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

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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


  • 2
    noYou  commented on July 21, 2020, 2: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.


  • 4
    op8  commented on July 2, 2020, 4: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. 10, 2018, 7:18 p.m.

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


    • -3
      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)


  • 4
    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.