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

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.

- The first line contains three integers: R, C and T:
the number of rows and columns of the map, and the number of tasks available.
- Each of the next R lines contains C integers:
the heights of the corresponding squares on the map.
- Each of the next T lines contains three integers: the row and column of
the task on the map, and the purity value gained when performing the task.
There can be at most one task in each square, and a given task can only be
performed once.
- The last line contains two integers: the row and column of the
temple on the map.

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`.

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

3

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.

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.

- For Subtask 1 (25 pts), R, C ≤ 100, heights ≤ 100, T ≤ 1,000, task purities ≤ 100.
- For Subtask 2 (25 pts), R, C ≤ 1,000, heights ≤ 1000, T ≤ 1,000, task purities ≤ 100.
- For Subtask 3 (50 pts), R, C ≤ 1,000, heights ≤ 100,000, T ≤ 100,000, task purities ≤ 1,000.

Privacy
statement

© Australian Mathematics Trust 2001-2022

Page generated: 25 September 2022, 1:50am AEST