[JOI Spring Camp 2012/2013] 산악 구조대

문제 : https://oj.uz/problem/view/JOI13_mountain

---

R행 C열 그리드로 이루어진 산이 있다.

산의 각 격자는 서로 다른 고도를 가진다.

 

산 정상의 좌표 \((R_s, C_s)\)는 주어지며, 정상의 고도가 가장 높다.

그리고 인접한 두 격자 중, 정상과의 Manhattan distance가 더 큰 격자가 고도는 더 작다

 

산에 조난 사고가 발생하여, 해당 위치를 알아야 구조할 수 있다.

사고가 일어난 지점의 고도 X가 주어졌을 때, 사고가 일어난 지점을 찾는 문제

 

---

인터렉션

int Measure(int RM, int CM)

해당 위치의 고도를 반환해준다.

최대 1000번 호출 가능

 

void Pinpoint(int RP, int CP)

사소가 일어난 지점을 기록한다.

최종 정답을 기록하는 함수

 

 

제약

• 모든 고도는 1 이상 10억 이하
• R과 C는 만점 기준 최대 200

 

---

Preliminary

모든 격자가 정상과의 거리와 반비례하는 것은 아니다.

인접 격자에 한해서만 규칙이 성립된다.

 

풀이

정상 ▲과 고도를 확인할 위치 ★가 다음과 같다고 하자

 

★의 고도가 만약 X보다 작다면, 다음 X를 찾을 장소는 두 방향이 된다.

왜냐하면 정상과 가까워 질수록, 고도는 높아지기 때문이다.

반대로 ★의 고도가 X보다 크다면, 다음 X를 찾을 장소는 반대가 된다.

 

이러한 방법으로 고도를 찾는다면, search space는 정상을 둘러싼 모양이 된다.

하지만 이동 경로의 분기점이 있어, 제약 내에 사고가 일어난 지점을 못찾을 수 있다.

하지만 search space를 정상 기준으로 4분면으로 나눈다면, 분기 없이 사고가 일어난 지점을 찾을 수 있게 된다.

 

붉은 공간에서 ★의 고도가 만약 X보다 작다면, 정상과 가까운 방향은 한 방향이다.

붉은 공간에서 ★의 고도가 만약 X보다 크다면, 정상과 멀어지는 방향은 한 방향이다.

각 4분면마다, 정상과 멀어지는 방향과 가까워지는 방향은 한 방향이다.

4분면의 search space마다 그리도 탐색하면 \(O(R+C)\) 인터렉션 복잡도로 사고가 일어난 지점을 찾을 수 있다.