AIOC Banner

Problem: Algo-Fu

Want to try solving this problem? You can submit your code online if you log in or register.


Algo-fu

Time Limit: 3 seconds
Memory Limit: 128 MB
Input File: standard input
Output File: standard output

You are on your way to the algo-fu temple, hidden in the mountains, where you plan to become a master of algo-fu. To receive the teachings of the monks, you first need to prove that your heart is pure.

You are given a map that represents the mountains as a rectanglular grid of squares, each having a height. You may move from your current square to any adjacent square on the map (east, west, north or south), as long as the new square's height is lower or equal to the purity value of your heart.

As you arrive into the top-left corner of the grid (which is row 1, column 1, and is guaranteed to have a height of 0) your heart is already tainted by the impurity of modern civilization, thus has a purity value of 0. Some of the squares may offer you an opportunity to perform a task which will add a certain amount of purity to your heart, allowing you to reach new heights. Your goal is to minimize the number of tasks that you will have to perform to reach the temple.

Input

Output

Output should consist of one line containing one integer: the minimum number of tasks that you need to perform in order to move to the square of the temple. If it is impossible to reach the temple, output -1.

Sample Input

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

Sample Output

3

Explanation

The map consists of 5 rows and 4 columns, with heights ranging from 0 to 9.

There are 4 tasks available, all in the first two columns of the map, as shown on the left side of the illustration below. The temple is in the last column, on the 4th row. It can be reached by performing the 3 tasks of the second column, following the path shown on the right side of the illustration.

The first task adds 1 to the purity value of your heart. It allows you to reach the second task of colum 2, which adds 2 to your purity, for a total of 3. You can then reach the third task of column 2, which adds 4 to your purity, for a total of 7, enough for you to reach the temple.

Subtasks

For all subtasks, R ≥ 1, C ≥ 1, T ≥ 0, all heights are at least 0, task purities are at least 1, and all task and temple positions have a row between 1 and R inclusive, and a column between 1 and C inclusive.

 


Privacy statement
© Australian Mathematics Trust 2001-2019

Contact: training@orac.amt.edu.au
Page generated: 24 May 2019,  3:50am AEST