Problem Description
A scientist wants to study how the rising sea level changes the landscape, in particular, how it changes the number of islands. He first investigates one-dimensional worlds. An one-dimensional world is represented by a sequence of positive integers (h0, h1, ..., hn-1), where each integer hi is the altitude at the location i. The following figure depicts an example of such world represented by the sequence (5, 6, 1, 3, 2, 9, 8).
Now, if the sea level is at altitude 2.5, there are 3 islands formed by landmass of the first two columns, the fourth column and the last two columns. Furthermore, if the sea level is at altitude 3.5, there are only 2 islands. When the sea level is altitude x, landmass with altitude x is considered to be submerged under the sea. Hence, if the sea level is at altitude 3, there are 2 islands. Note that having 3 islands is the maximum among all the possible sea levels.
Wait wait wait, doesn't this sound like NOI!? During NOI, the scientist wants to find the maximum number of islands among all sea levels. Thanks to many programmers, he was able to conclude his research on sea levels in one-dimensional worlds. But one-dimensional worlds aren't very common and thus his paper did not get published. Now, he wants to investigate two-dimensional worlds!
Now, instead of a sequence of positive integers, there will be a H x W grid of positive integers not exceeding 2 billion. Similarily, the scientist wants to find the maximum number of islands among all the sea levels.
For clarity, two points belong to the same island when it is possible to reach each other directly or indirectly by going up, down, left or right adjacent points only. (No diagonal)
Input
The first line of input will contain 2 integers, H and W. These are the height and width of the grid of positive integers.
H lines will follow with W integers each. These describe the height of the terrain the scientist is investigating.
Output
Output a single integer, the maximum number of islands among all the sea levels.
Subtasks
Subtask 1 (9%): H = 1, W ≤ 1000. In addition, no point will have a height greater than 1000.
Subtask 2 (8%): H = 1, W ≤ 1000000
Subtask 3 (37%): H ≤ 50, W ≤ 50
Subtask 4 (46%): H * W ≤ 1000000 (There are at most 1000000 integers in the grid)
Subtask 5 (0%): Sample
Sample Input
4 7
5 6 1 3 2 9 8
1 3 2 4 5 7 6
9 1 2 3 4 1 3
1 2 1 2 1 2 1
Sample Output
4
When the sea level is 1.5m, there will be 4 islands as the following places will be submerged. This is the maximum for all the sea levels.
5 6 x 3 2 9 8
x 3 2 4 5 7 6
9 x 2 3 4 x 3
x 2 x 2 x 2 x