The Flood

Interview

Time limit1sMemory limit128 MB

Summary
Given a grid of altitudes, find the lowest water level at which the dry land splits into two or more connected pieces, where water floods inward from outside.
Level

Medium6 of 10

Topics
Graph, Union-find, Sorting, BFS
Solved
No attempts yet

Problem

Rising oceans have the small island nation of Gonnasinka worried: they want to know how high the water must rise before their single island becomes two or more islands.

You are given a grid of integers giving the altitudes of the island, and the ocean surrounds the grid. As the ocean rises to a level of ff feet, water spreads inward from outside: a cell becomes submerged if its altitude is at most ff and it can be reached from outside the grid through a path of horizontally or vertically adjacent cells each having altitude at most ff. A low area that is completely enclosed by higher land stays dry until that surrounding barrier is overtopped. Determine how high the ocean must rise before the cells that are still dry form two or more separate connected pieces.

Input

Each test case begins with a line containing two positive integers nn and mm, the dimensions of the grid, followed by nn lines each containing mm non-negative integers, the altitudes of the cells. Two cells are adjacent only when they share a horizontal or vertical edge, and the ocean initially surrounds the grid at level 00.

Consequently, a cell of altitude 00 on the perimeter, together with every altitude-00 cell connected to it through other altitude-00 cells, is ocean at this initial level, while an altitude-00 cell not connected to the perimeter (enclosed by higher land) is dry land at sea level. The island is initially a single connected piece. Neither nn nor mm exceeds 100100, and no altitude exceeds 10001000. A line containing 0 0 follows the last test case and is not processed.

Output

For each test case, output exactly one of the following two lines. If the land eventually splits, output

Case n: Island splits when ocean rises f feet.

where n is the test case number (starting from 11) and f is the smallest whole number of feet the ocean must rise to break the land into two or more pieces. Otherwise output

Case n: Island never splits.

By convention, an answer of ff feet means ff feet plus a little more: at least a little water flows over the land that was originally ff feet high, so a cell of altitude ff counts as submerged once the ocean reaches ff feet.

Examples1

  1. Example 1

    Input
    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
    Expected output
    Case 1: Island never splits.
Case 2: Island splits when ocean rises 3 feet.