Rated Contest 2 P2 - A-ski-ng Around

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type

Having now finalized which ski resort to stay at, it's time for Daniel to invite his friends! However, as it is winter, Daniel is unsure if all of his N friends can make the drive to the resort. Thus, he will first make some calculations before asking around to see who is interested.

The location of the resort relative to each of his friends can be modelled by an M-by-M kilometre grid, with each friend located somewhere in the grid (possibly in the same square as another friend) and the ski resort itself located in the bottom-right corner. In addition, each square kilometre of land has a snow-elevation height, and thus it is only possible to drive into adjacent squares if the absolute difference in snow-elevation is less than or equal to H.

Can you help Daniel determine how many of his friends can make the drive?

Constraints

1 \le H \le 10^3

Snow-elevation heights are integer values between 1 and 10^3.

Subtask 1 [40%]

1 \le N, M \le 10

Subtask 2 [60%]

1 \le N, M \le 10^3

Input Specification

The first line of input will contain N, M, and H.

The next N lines each contain two integers, i and j, indicating a friend in the i-th row and j-th column of the grid.

The last M lines will each contain M integers, the snow-elevation height of every square in the row.

Output Specification

Output one integer, the number of friends that can make the drive to the resort.

Sample Input 1

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

Sample Output 1

1

Sample 1 Explanation

The first friend is trapped in their starting position! They cannot drive outside of cell (1, 1). The second friend can go left, then down two squares, then right to reach the resort.

Sample Input 2

5 5 10
1 3
1 4
2 2
3 5
4 1
8 2 4 5 3
3 5 5 8 8
9 2 3 4 5
5 2 4 5 3
5 2 3 7 100

Sample Output 2

0

Comments

There are no comments at the moment.