Safe Areas

A disaster-prevention agency is studying the height map of a region. The region is given as an N x N grid, and each cell contains a positive integer height.

If the rain amount is h, every cell with height at most h is submerged. A safe area is one connected group of unsubmerged cells, where cells are connected only in the four directions: up, down, left, and right. Cells touching only at a corner are not connected.

For example, suppose N=5 and the region has the following heights.

When the rain amount is 4, only cells with height at least 5 remain, and there are 5 safe areas. When the rain amount is 6, only cells with height at least 7 remain, and there are 4 safe areas. Thus, the number of safe areas depends on the rain amount.

Also consider the case where no rain falls and no cell is submerged. Given the height map of a region, compute the maximum possible number of safe areas over all rain amounts.

The first line contains N, the side length of the region. N is an integer between 2 and 100, inclusive.

The next N lines contain the height map, one row per line. Each row contains N positive integers separated by spaces, and every height is between 1 and 100, inclusive.

Print the maximum possible number of safe areas over all rain amounts.

You must also consider the case where no rain falls and no part of the region is submerged.