The Flood#1190
Global warming has us all thinking of rising oceans — well, maybe only those of us who live near the ocean. The small island nation of Gonnasinka has asked you to answer some questions for them. In particular, they want to know how high the water has to rise before their island splits into two or more islands.
Given a grid of integers representing the altitudes of the island, how high must the ocean rise before the land splits into pieces?
Each test case begins with a line containing two positive integers , giving the dimensions of the grid. Then lines follow, each containing positive integers. These integers indicate the original altitude of the grid elements. Grid elements are considered adjacent only if they share a horizontal or vertical edge. Values of zero () along the perimeter and all zero cells connected to them represent ocean at its initial level. Zero () cells not connected to the perimeter (that is, surrounded by higher land) are simply sea level elevations. Furthermore, assume the ocean initially surrounds the given grid. The island is initially connected. Neither nor will exceed , and heights will never exceed . A line with follows the last test case.
For each test case, output one of the following two lines:
Case : Island splits when ocean rises feet.
or
Case : Island never splits.
Our convention here is that if your answer is, say, 5 feet, you more accurately mean "5 feet plus a little more." That is, at least a little water will flow over the portion of land that is originally feet high.
Example 1