PROBLEM STATEMENT
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).
DEFINITION
Class:DonutsOnTheGridEasy
Method:calc
Parameters:vector
Returns:int
Method signature:int calc(vector grid)
CONSTRAINTS
-grid will have between 1 and 50 elements, inclusive.
-Each element of grid will have between 1 and 50 characters, inclusive.
-All elements of grid will have the same length.
-Each character of grid will be either '0' (zero) or '.'.
EXAMPLES
0)
{"0000000"
,"0.....0"
,"0.00000"
,"0.0..00"
,"0.00000"
,"0.....0"
,"0000000"}
Returns: 2
1)
{"000"
,"0.0"
,"000"}
Returns: 1
2)
{"..."
,"..."
,"..."}
Returns: 0
3)
{"00.000"
,"00.000"
,"0.00.0"
,"000.00"}
Returns: 0
4)
{"0000000....",
"0000000....",
"0000000.000",
"0000000.0.0",
"0000000.000",
"0000000....",
"0000000...."}
Returns: 3
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.