DWITE '10 R4 #4 - Mountain Hiking

View as PDF

Submit solution

Points: 7
Time limit: 2.0s
Memory limit: 64M

Problem type
DWITE Online Computer Programming Contest, January 2011, Problem 4

Mountain hiking is a very adventurous, yet somewhat dangerous, pastime. On certain mountain ranges, the heights could vary sharply. An amateur hiker can move to an adjacent (left/right, up/down, but not diagonally) location only if the height difference with the current location is at most 1. Given a height map of a mountain range, determine the distance of the shortest viable path between the left and the right edges.

The input will contain 5 test cases. Each test case consists of a 10 \times 10 map of digits 0 to 9, each digit representing the height of that location. A line of hyphens ---------- follows each test case for visual separation.

The output will contain 5 lines, the least number of steps to cross the mountain range in each case. If the hiker can't get across, output IMPOSSIBLE instead.

Notes: the hiker could start at any of the left-most positions. The steps counted are the transitions from one location to the next. Thus appearing in that very first location requires no steps.

Sample Input

9324892342
1334343293
3524523454
2634232043
0343259235
2454502352
4563589024
7354354256
9343221234
2653560343
----------

Sample Output

11

Attribution-NonCommercial-ShareAlike 3.0 Unported (CC BY-NC-SA 3.0) Problem Resource: DWITE


Comments


  • 1
    RyanLi  commented on Aug. 13, 2019, 9:48 a.m.

    the lest number of steps

    Typo on least