| 2025 ICPC, Chula Selection Contest |
|---|
| Закончено |
The Royal Bangkok Sports Club is preparing new endurance training for special horses. The racecourse is an $$$n × m$$$ grid of rectangular fields. Each field $$$(i, j)$$$ has a difficulty rating $$$D_{i,j}$$$. A higher value means the road there is rougher and requires more effort from the horse. Some fields are soft grass, while others are bumpy and uneven, demanding very high effort. Horses can move between two fields if they share a common side (up, down, left, and right).
For training, the committee designs tasks as follows:
The effort of a training route is defined as the maximum difficulty among all fields the horse must step on during the route.
The horse may choose any order to visit the fields, and the committee only cares about the minimum possible effort. There are $$$q$$$ tasks, and you must report all of them!
The first line contains three integers $$$n, m, q$$$ $$$(1 \leq n, m \leq 500)$$$ and $$$(1 \leq q \leq 10^5)$$$.
The next $$$n$$$ lines each contain $$$m$$$ integers, giving the difficulty ratings $$$D_{i,j}$$$ of the fields.
Each of the next q lines describes one query with six integers $$$r, c, r_1, c_1, r_2, c_2$$$
For each query, print a single integer — the minimum effort required for that horse's route.
3 4 25 1 7 76 4 2 89 3 3 32 2 1 2 2 31 1 2 2 3 3
7 5
These are the moves that results in the minimum cost.
Other routes may exist, but whichever path is chosen, the minimum possible effort should be the same.
| Название |
|---|


