# 221. Maximal Square 最大正方形

@TOC

## # 题目描述

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

Example:

``````Input:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Output: 4
``````

## # 解题方法

### # 动态规划

1. dp[0][j] = matrix[0][j] (topmost row);
2. dp[i][0] = matrix[i][0] (leftmost column);
3. For i > 0 and j > 0: if matrix[i][j] = 0, dp[i][j] = 0; if matrix[i][j] = 1, dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1.

``````class Solution(object):
def maximalSquare(self, matrix):
"""
:type matrix: List[List[str]]
:rtype: int
"""
if not matrix: return 0
M = len(matrix)
N = len(matrix[0])
dp = [[0] * N for _ in range(M)]
for i in range(M):
dp[i][0] = int(matrix[i][0])
for j in range(N):
dp[0][j] = int(matrix[0][j])
for i in range(1, M):
for j in range(1, N):
if int(matrix[i][j]) == 1:
dp[i][j] = min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) + 1
return max(map(max, dp)) ** 2
``````

C++代码如下：

``````class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
if (matrix.size() == 0 || matrix[0].size() == 0) return 0;
const int M = matrix.size(), N = matrix[0].size();
vector<vector<int>> dp(M, vector<int>(N, 0));
int res = 0;
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
if (i == 0 || j == 0)
dp[i][j] = matrix[i][j] - '0';
else if (matrix[i][j] == '1')
dp[i][j] = min(dp[i - 1][j], min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
res = max(res, dp[i][j]);
}
}
return res * res;
}
};
``````