홍수

면접 대비

시간 제한1초메모리 제한128 MB

요약
고도 격자가 주어질 때, 바깥에서 물이 차오르는 상황에서 남은 육지가 두 개 이상의 연결 요소로 갈라지는 최소 수위를 구한다.
난이도

보통10점 중 6점

유형
그래프, 유니온 파인드, 정렬, BFS
정답자
아직 제출이 없습니다

문제

해수면 상승 때문에 작은 섬나라 고나싱카는 걱정이 많다. 이들은 물이 얼마나 높이 차오르면 하나였던 섬이 두 개 이상의 섬으로 나뉘는지 알고 싶어 한다.

섬의 고도를 나타내는 정수 격자가 주어지며, 바다가 이 격자를 둘러싸고 있다. 바다가 높이 ff 피트까지 차오르면, 물은 바깥에서 안쪽으로 퍼진다. 어떤 칸은 그 고도가 ff 이하이고, 격자 바깥에서부터 고도가 모두 ff 이하인 칸들을 상하좌우로 인접하게 지나는 경로로 도달할 수 있을 때 물에 잠긴다. 더 높은 땅으로 완전히 둘러싸인 낮은 지역은 그 둘러싼 장벽이 넘칠 때까지 마른 상태로 남는다. 아직 물에 잠기지 않은(마른) 칸들이 서로 떨어진 두 개 이상의 연결된 조각을 이루게 되려면 바다가 얼마나 높이 차올라야 하는지 구하여라.

입력

각 테스트 케이스는 두 양의 정수 nn 과 mm(격자의 크기)이 적힌 줄로 시작하고, 이어서 nn 개의 줄에 각각 mm 개의 음이 아닌 정수(각 칸의 고도)가 주어진다. 두 칸은 상하좌우로 변을 맞댈 때에만 인접하며, 바다는 처음에 높이 00 으로 격자를 둘러싸고 있다.

따라서 격자 가장자리에 있는 고도 00 인 칸과, 다른 고도 00 인 칸들을 통해 그것과 연결된 모든 고도 00 인 칸은 이 초기 수위에서 바다이며, 가장자리와 연결되지 않은(더 높은 땅으로 둘러싸인) 고도 00 인 칸은 해수면 높이의 마른 땅이다. 섬은 처음에 하나로 연결되어 있다. nn 과 mm 은 각각 100100 을 넘지 않으며, 어떤 고도도 10001000 을 넘지 않는다. 마지막 테스트 케이스 뒤에는 0 0 이 적힌 줄이 오며, 이 줄은 처리하지 않는다.

출력

각 테스트 케이스마다 다음 두 줄 중 정확히 하나를 출력한다. 땅이 언젠가 나뉘는 경우에는

Case n: Island splits when ocean rises f feet.

를 출력하며, 여기서 n 은 (11 부터 시작하는) 테스트 케이스 번호이고, f 는 땅을 두 개 이상의 조각으로 나누기 위해 바다가 차올라야 하는 가장 작은 정수 피트 값이다. 그렇지 않으면

Case n: Island never splits.

를 출력한다. 관례상 답이 ff 피트라는 것은 ff 피트에 아주 조금 더한 것을 뜻한다. 즉, 원래 높이가 ff 피트였던 땅 위로 적어도 아주 약간의 물이 흐르므로, 바다가 ff 피트에 이르면 고도 ff 인 칸은 잠긴 것으로 본다.

예제1

  1. 예제 1

    입력
    5 5
3 4 3 0 0
3 5 5 4 3
2 5 4 4 3
1 3 0 0 0
1 2 1 0 0
5 5
5 5 5 5 7
4 1 1 1 4
4 1 2 1 3
7 1 0 0 4
7 3 4 4 4
0 0
    예상 출력
    Case 1: Island never splits.
Case 2: Island splits when ocean rises 3 feet.