| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 4 초 | 2048 MB | 38 | 17 | 15 | 44.118% |
The JOI Mountain Range consists of many mountains. It is represented as a grid with $H$ rows and $W$ columns, where the north-south direction is vertical, and the east-west direction is horizontal. The cell at the $i$-th row from the north ($1 ≤ i ≤ H$) and the $j$-th column from the west ($1 ≤ j ≤ W$) is denoted as $(i, j)$. There is exactly one mountain in each cell. The height of the mountain at cell $(i, j)$ is $T_{i, j}$.
Bitaro, the beaver, can move between the summits of the mountains using the procedure called high jump, which is described below. Here, $L$ is the parameter for his jumping skill.
Bitaro is planning for $Q$ trips. In the $k$-th trip ($1 ≤ k ≤ Q$), he plans to move from the summit of the cell $(A_k, B_k)$’s mountain to the summit of the cell $(C_k, D_k)$’s mountain by only using high jumps. He wants to know if these trips are possible, and if so, he also wants to know the minimum number of high jumps needed, because high jumps require much energy.
The information on the mountains, Bitaro’s jumping skill, and his trip plans, are given. Write a program that, for each trip plan, determines whether it is possible, and calculates the minimum number of high jumps needed if the trip is possible.
Read the following data from the standard input.
$H$ $W$ $L$
$T_{1,1}$ $T_{1,2}$ $\cdots$ $T_{1,W}$
$T_{2,1}$ $T_{2,2}$ $\cdots$ $T_{2,W}$
$\vdots$
$T_{H,1}$ $T_{H,2}$ $\cdots$ $T_{H,W}$
$Q$
$A_1$ $B_1$ $C_1$ $D_1$
$A_2$ $B_2$ $C_2$ $D_2$
$A_Q$ $B_Q$ $C_Q$ $D_Q$
Write $Q$ lines to the standard output. In the $k$-th line ($1 ≤ k ≤ Q$), output the minimum number of high jumps needed in the $k$-th trip if the trip is possible. If the trip is impossible, output -1.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 10 | $H \times W ≤ 300$, $Q ≤ 150\, 000$. |
| 2 | 20 | $H \times W ≤ 3\,000$, $Q ≤ 150\, 000$. |
| 3 | 20 | $H \times W ≤ 150\,000$, $Q ≤ 150\, 000$, $(A_k, B_k) = (1, 1)$ ($1 ≤ k ≤ Q$). |
| 4 | 30 | $H \times W ≤ 150\,000$, $Q ≤ 150\, 000$. |
| 5 | 20 | No additional constraints. |
2 4 5 1 3 22 1 8 13 6 16 6 1 1 2 2 1 1 1 3 1 1 2 3 1 1 2 4 1 1 1 4 1 1 1 2
3 -1 3 4 4 1
For the first trip, Bitaro can move from the summit of the mountain at cell $(1, 1)$ to the summit of the mountain at cell $(2, 2)$ by using $3$ high jumps, in the following way:
It is impossible to end the first trip with less than $3$ high jumps. Therefore, output $3$ in the first line. For the second trip, it is impossible to realize the trip. Therefore, output -1 in the second line. This sample input satisfies the constraints of all subtasks.
6 5 11 175 100 110 117 158 144 133 123 150 191 167 252 219 181 346 231 241 280 201 209 261 332 325 225 338 269 298 315 291 308 12 1 1 4 2 1 1 1 5 1 1 5 1 1 1 5 4 1 1 3 4 1 1 6 4 1 1 2 5 1 1 3 1 1 1 4 4 1 1 5 5 1 1 6 2 1 1 6 1
8 1 10 6 1 13 2 1 3 19 14 11
This sample input satisfies the constraints of all subtasks.
4 4 5 53 55 51 49 56 60 89 45 54 57 92 43 96 99 95 92 9 1 4 2 3 4 1 3 2 2 4 2 3 2 1 4 1 1 2 1 1 2 4 1 1 4 1 2 3 3 4 1 1 1 3 1 4
-1 1 -1 -1 1 3 1 4 1
This sample input satisfies the constraints of Subtasks 1, 2, 4, and 5.