SquareCutout
2018 TCO Fun 3B · 2018-04-20 · by misof
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
If the bitmap can represent a part of the Xanadu plane, return the smallest N that is consistent with cutout. Otherwise, return zero.
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 '#'.
{".....",
"..##.",
"..##.",
".....",
"....."}
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.
Submissions are judged against all 260 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class SquareCutout with a public method int verify(vector<string> cutout) · 260 test cases · 2 s / 256 MB per case