Largest Square
InterviewTime limit1sMemory limit128 MB
Given a binary grid, find the area of the largest square consisting entirely of 1s using dynamic programming.
- Level
Medium4 of 10
- Topics
- Dynamic programming, Matrix
- Solved
- No attempts yet
Problem
You are given an n x m grid made of 0s and 1s. Find the largest-area square in the grid whose every cell is 1.
Print the area of the square, not its side length.
Input
The first line contains two integers n and m. (1 <= n, m <= 1,000)
Each of the next n lines contains one string of length m consisting only of 0s and 1s.
Output
Print the area of the largest square whose every cell is 1.