Largest Square of 1s
mediumMatrix+20 XPTime limit 2s
A plot of land is drawn as a grid: 1 is a usable square metre, 0 is a rock. You want to build a square house on usable land only. Find the area of the largest all-1 square in the grid.
Input:
- line 1:
r c - next
rlines:cvalues, each0or1
Output: the area of the largest square containing only 1s (0 if there is no 1).
Constraints: 1 ≤ r, c ≤ 500.
Think about it: let dp[i][j] be the side of the largest all-1 square whose bottom-right corner is (i, j). If the cell is 1, dp[i][j] = 1 + min(top, left, top-left) — the square can only grow as far as all three neighbours allow.
Sample input 1
4 5 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0
Sample output 1
4
Sample input 2
2 2 0 1 1 0
Sample output 2
1
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).