등산가
시간 제한7초메모리 제한512 MB
격자 위 두 칸 사이를 상하좌우로 이동할 때 지나는 칸 높이의 최댓값을 최소로 하는 값을 각 질의마다 구한다.
문제
칠레 안데스 산맥은 배낭 여행과 하이킹 목적지로 점점 인기를 얻고 있다. 안데스의 많은 지역은 매우 외지고 위험하다. 그래서 관광부는 여행자들이 여행을 계획하도록 돕고자 한다. 특히 여행자들은 여정 중에 얼마나 높이 올라가야 하는지 알아야 하는데, 이 정보는 어떤 장비를 가져갈지 결정하는 데 도움이 된다. 관광부는 여러분에게 이 데이터를 제공하도록 요청했다.
높이 값의 2차원 격자로 표현된 안데스 일부 지역의 지형도와 출발지와 목적지의 목록이 주어진다. 등산가는 각 격자 칸에서 인접한 네 칸 중 어느 곳으로든 이동할 수 있다. 각 등산가마다 여정을 완수하기 위해 도달할 수 있어야 하는 최소 높이를 구하여라.
입력
입력은 다음과 같다.
- 세 정수 m, n, q가 있는 한 줄 (1 ≤ m, n ≤ 500, 1 ≤ q ≤ 10^5). 여기서 m은 행의 수, n은 열의 수, q는 등산가의 수이다.
- m개의 줄. 각 줄에는 n개의 정수 h1, . . . , hn (1 ≤ hi ≤ 10^6)이 있으며, 지도의 높이 값이다.
- q개의 줄. 각 줄에는 네 정수 x1, y1, x2, y2 (1 ≤ x1, x2 ≤ m, 1 ≤ y1, y2 ≤ n)가 있으며, (x1, y1)에서 (x2, y2)로 이동하려는 등산가를 나타낸다.
격자의 왼쪽 위 칸은 좌표 (1, 1)이고, 오른쪽 아래 칸은 좌표 (m, n)이다.
출력
q개의 정수를 입력 순서대로 출력한다. 각 정수는 해당 등산가의 최소 높이이다.