题解 | #最大正方形#

class Solution {
public:
    /**
     * 最大正方形
     * @param matrix char字符型vector<vector<>> 
     * @return int整型
     */
    int solve(vector<vector<char> >& matrix) {
        // write code here
        int res = 0;
        int n = matrix.size();
        int m = matrix[0].size();
        if(n < 1 || m < 1)
            return res;
        vector<vector<int>> dp(n,vector<int>(m, 0));
        for(int i = 0; i < m; i++)
            if(matrix[0][i] == '1') {
                dp[0][i] = 1;
                res = 1;
            }
        for(int i = 0; i < n; i++)
            if(matrix[i][0] == '1') {
                dp[i][0] = 1;
                res = 1;
            }
        
        if(n < 2 && m < 2)
            return res;
        for(int i = 1; i < n; i++) {
            for(int j = 1; j < m; j++) {
                if(matrix[i][j] == '1') {
                    int a = min(dp[i][j - 1], dp[i - 1][j]);
                    dp[i][j] =min(a , dp[i - 1][j - 1]) + 1;
                    res = max(dp[i][j], res);
                }
            }
        }
        return res * res;
    }
};