보물 지도 timer 4s memory 2048MB

수년간의 수색 끝에, 해저 깊숙이 숨겨진 블랙비어드의 오랜 보물 지도를 발견했다. 이 지도는 원래 등심선 지도(하이프소메트릭 맵)로, 보물 주변 바다의 수심을 보여 주었지만, 시간이 지나 많은 수심 표기가 희미해져 더 이상 읽을 수 없게 되었다.

구체적으로, 지도는 바다의 직사각형 영역을 다루며, 이를 (n - 1) \times (m - 1)개의 단위 정사각형으로 분할한다. 원래 지도는 정수 좌표 1 \le; x \le; n, 1 \le; y \le; m인 모든 점 p = (x, y)에 대해 수심 d(p)를 표시했다. 그 영역에는 섬이 없으므로, 모든 점에 대해 d(p) ≥ 0임을 알고 있다.

블랙비어드는 정수 격자가 아닌 점의 수심을 보간해야 했기에, 자연스러운 방법이 하나로 정해지지 않는다. 격자에서 한 단위 정사각형을 생각하자. 꼭짓점은 시계 방향으로 A, B, C, D이고, 각 꼭짓점 p \in \{A, B, C, D\}에 수심 d(p)가 주어진다. 한 가지 방법은 삼각형 ABC에서 선형 보간하고, 마찬가지로 CDA에서 선형 보간하는 것이다. 또 다른 자연스러운 방법은 BCD에서 선형 보간하고, DAB에서 선형 보간하는 것이다. 대체로 두 방법의 결과는 다르다. 예를 들어 d(A) = d(B) = d(C) = 0이고 d(D) = 1이면, 첫 번째 방법은 ABC 전체의 수심이 0이 되지만(그림 K.1 왼쪽), 두 번째 방법은 정사각형의 내부 전체가 양의 수심을 갖게 된다(오른쪽).

그림 K.1: 단위 정사각형 내 수심 보간의 두 가지 방법.

그러나 블랙비어드는 집요하고 완고하여, 이런 골치 아픈 모호함이 그를 막게 두지 않았다. 그는 보물을 숨길 완벽한 장소를 찾기 위해, 위 두 방법이 모든 단위 정사각형에서 동일한 결과를 내는 바다 구역을 찾아 다녔다(혹은 이를 위해 해적들에게 간단한 지형 공사를 시켰다는 학설도 있다).

현재 당신은 보물을 회수하기 위한 탐사를 준비하고 있으며, 보물이 묻혔을 수심이 어느 정도인지 알고 싶다. 구체적으로, 남아 있는 수심 데이터가 주어졌을 때 보물 위치에서 가능한 최소 수심을 계산하라.