Petya likes donuts. He tries to find them everywhere. For example if he is given a grid where each cell contains a '0' (zero) or '.' he will construct donuts from the cells.
To make the donuts:
- Petya first selects a rectangle of cells of width, w, and height, h, where both are at least 3.
- Then he removes a rectangular hole of width w-2 and height h-2 centered in the larger rectangle.
- For the remaining cells (a closed rectangular ring) to be a valid donut, all of the cells must contain '0' (because donuts are shaped like zeros). Cells in the hole can contain anything since they are not part of the donut.
An example of large donut containing a smaller donut.
..........
.00000000.
.0......0.
.0.0000.0.
.0.0..0.0.
.0.0..0.0.
.0.0000.0.
.0......0.
.00000000.
..........
Donuts may contain other donuts and donuts may touch, but the cells of one donut may not overlap the cells of another. Petra is most interested in donuts that contain other donuts. He first places one valid donut on the grid (if possible). He then places a valid donut in the hole of the first donut (if possible). He continues to place a donut into the hole of the most recently placed donut until this is no longer possible.
Your task is to find the maximum number of donuts that Petya can place on the grid as described such that each donut (except for the first) is contained within the previous donut. You are given grid, a String[], containing only '0' and '.' characters. The j-th character of the i-th element is the value at cell (i, j).
|