P11065 【MX-X4-T5】“Jason-1” Occupy the High Ground.

Original link: .

There is a map with $n$ rows and $m$ columns. The **height** of the cell in row $i$, column $j$ is $h_{i,j}$, and its **militarization level** is $p_{i,j}$. It satisfies that **for any two 4-directionally adjacent cells, the absolute difference of their heights is at most $\bm 1$**. (Two cells $(a, b)$ and $(c, d)$ are 4-directionally adjacent if and only if $\lvert a - c\rvert + \lvert b - d\rvert = 1$.) You may choose several cells to build supply stations. If a supply station is built at cell $(i, j)$, define its **transport range** as all cells $(x, y)$ satisfying $h_{i,j} - h_{x,y} + p_{i,j} \geq \lvert i - x\rvert + \lvert j - y\rvert$. Each supply station can move supplies between any cells within its transport range. Define the security level of several supply stations $(x, y)$ as the minimum value among their $h_{x,y}$. There are $q$ queries. Each query gives four integers $a, b, c, d$ and asks: if you want to build some supply stations to transport supplies from cell $(a, b)$ to cell $(c, d)$, what is the maximum possible security level of the stations you build? Or report that it is impossible to complete the transport task. **Note: supplies can be transported indirectly through multiple supply stations. It is not necessary to build stations at $(a, b)$ and $(c, d)$.** **This problem guarantees $\bm{p_{i, j} \le 9}$.**

The first line contains three positive integers $n, m, q$, representing the number of rows, the number of columns, and the number of queries. The next $n$ lines each contain $m$ non-negative integers. The integer in row $i$, column $j$ represents the height $h_{i,j}$. **It is guaranteed that for any two 4-directionally adjacent cells, the absolute difference of their heights is at most $\bm 1$.** The next $n$ lines each contain $m$ non-negative integers. The integer in row $i$, column $j$ represents the militarization level $p_{i,j}$. **It is guaranteed that $\bm{p_{i, j} \le 9}$.** The next $q$ lines each contain four positive integers $a, b, c, d$, representing a query.

Output $q$ lines. The $i$-th line contains one integer, representing the answer to the $i$-th query, i.e. the maximum security level that allows supplies to be transported from $(a, b)$ to $(c, d)$. If the transport task cannot be completed no matter how many supply stations are built, output $-1$.

**[Sample Explanation #1]** For the first query, you can build a supply station at $(1, 3)$, and the security level is $3$. For the second query, you can build a supply station at $(4, 1)$, and the security level is $4$. For the third query, you can build a supply station at $(3, 2)$, and the security level is $3$. For the fourth query, you can build a supply station at $(3, 2)$, and the security level is $3$. For the fifth query, you can build a supply station at $(4, 1)$, and the security level is $4$. For the sixth query, you can build supply stations at $(4, 1)$ and $(1, 3)$, and the security level is $3$. **[Sample Explanation #2]** Only a supply station built at $(1, 1)$ can move supplies freely between $(1, 1)$ and $(1, 2)$. A supply station built at any other cell will not be able to move any supplies. Therefore, only query $1$ can be achieved. You only need to build a supply station at $(1, 1)$, and the security level is $1$. **[Constraints]** **This problem uses bundled testdata.** | Subtask | $q \le$ | $n, m \le$ | Special Property | Score | | :----------: | :----------: | :----------: | :----------: | :----------: | | 1 | $20$ | $10$ | A | $23$ | | 2 | $10^5$ | $300$ | B | $19$ | | 3 | $10^5$ | $100$ | None | $27$ | | 4 | $2 \times 10^5$ | $300$ | None | $31$ | - Special property A: $p_{i, j} \le 4$. - Special property B: $p_{i, j} = 0$. For $100\%$ of the testdata, $1 \le n, m \le 300$, $0 \le h_{i,j} \le 10^9$, $\bm{0 \le p_{i,j} \le 9}$, $1 \le q \le 2 \times 10^5$, $1 \le a, c \le n$, $1 \le b, d \le m$, $(a, b) \neq (c, d)$, and **it is guaranteed that for any two 4-directionally adjacent cells, the absolute difference of their heights is at most $\bm 1$**. Translated by ChatGPT 5