← 返回 salesforce 的题目列表Maximal Square
类型：online_judge
Maximal Square
Given an m × n matrix matrix containing only characters '0' and '1', find the largest square consisting entirely of '1's and return its area.
In the interview, explain in order:
A brute-force solution with its time and space complexity;
An optimal solution with its time and space complexity;
An implementation of the optimal solution.
Input Format
First line: two integers m n, the number of rows and columns.
Next m lines: a string of length n containing only '0' and '1'.
Output Format
Print one integer: the area of the largest all-'1' square.
Constraints
1 <= m, n <= 300
matrix[i][j] is either '0' or '1'
Example 1
Input:
4 5
10100
10111
11111
10010
Output:
4
The largest all-'1' square has side length 2 and area 4.
Example 2
Input:
2 2
01
10
Output:
1
Example
Input
4 5
10100
10111
11111
10010
Output
4