A fortress plan is a grid of R rows and C columns. A cell holds 1 where stone is laid and 0 where it is missing. A parapet is any axis-aligned square whose border cells (the top and bottom rows of the square and its left and right columns) are all 1; the cells strictly inside the square may be anything. A single 1 cell counts as a 1-by-1 parapet.
Determine the area (side length squared) of the largest parapet. If no cell is 1, the area is 0.
Line 1: two integers R and C.
Next R lines: each contains C integers, each 0 or 1.
A single integer: the area of the largest square with an all-1 border, or 0 if there is none.
Example 1
Input
3 3 1 1 1 1 0 1 1 1 1
Expected
9
Explanation
The whole 3x3 has an all-1 border even though its center is 0, so the largest parapet has side 3 and area 9.
Example 2
Input
1 4 1 1 0 0
Expected
1
Explanation
No 2x2 or larger border exists, but single 1 cells are 1x1 parapets, so the largest area is 1.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →