221.最大正方形

221. 最大正方形

难度中等332

在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。

示例:

输入: 

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

输出: 4

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int n = matrix.size();
        if(n==0){
            return 0;
        }
        int m = matrix[0].size();
        int ret =0;
        int dp[n+5][m+5];
        memset(dp,0,sizeof dp);
        for(int i = 0;i<n;i++){
            for(int j = 0;j<m;j++){
                if(matrix[i][j]=='1'){
                    if(i==0 || j==0){
                        dp[i][j] = 1;
                    }
                    else {
                        dp[i][j] = min(min(dp[i-1][j-1],dp[i-1][j]),dp[i][j-1])+1;
                    }
                    ret = max(ret,dp[i][j]);
                }
            }
        }
        return ret*ret;
    }
};