SquareCutout | Topcoder Archive

Problem Statement

There once was an infinite plane called Xanadu. The plane was divided into a grid of unit square cells. The entire plane was white, with one exception: a black square. More precisely, for some unknown positive integer N there was an N times N square that consisted of N^2 black cells.

Your friend recently showed you a rectangle. She claims that she cut it out of the Xanadu plane, and that she was cutting along grid lines while doing so. Verify her story.

You are given the String[] cutout that represents a rectangular bitmap. The character '.' represents a white cell and the character '#' represents a black cell.

If the bitmap can represent a part of the Xanadu plane, return the smallest N that is consistent with cutout. Otherwise, return zero.

Definition

Class:: SquareCutout
Method:: verify
Parameters:: String[]
Returns:: int
Method signature:: int verify(String[] cutout)
(be sure your method is public)

Constraints

cutout will contain between 1 and 50 elements, inclusive.
Each element of cutout will contain between 1 and 50 characters, inclusive.
Each element of cutout will contain the same number of elements.
Each character of each element of cutout will be either '.' or '#'.

Examples

```
{".....",
 "..##.",
 "..##.",
 ".....",
 "....."}
```
```
Returns: 2
```
This is very clearly a cutout that contains the entire square. The length of its side is 2.
```
{"...",
 "..."}
```
```
Returns: 1
```
It is possible that this is a cutout made from Xanadu. The square was simply somewhere else. The smallest size it can have is 1.
```
{".....",
 ".###.",
 ".#.#.",
 ".###.",
 "....."}
```
```
Returns: 0
```
This cutout is definitely not from Xanadu. The square must be filled completely.
```
{"..####",
 "..####",
 "......"}
```
```
Returns: 4
```
We may see the bottom left corner of a square. The square is at least 4x4. It may be even bigger, but 4 is the smallest size that matches what we see.
```
{"..#..",
 ".###.",
 "#####",
 ".###.",
 "..#.."}
```
```
Returns: 0
```
This is not a square. This is also not a part of any larger square.

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)2024, Topcoder, Inc. All rights reserved.