题解 | #最大正方形#

#include <algorithm>
#include <climits>
#include <cmath>
#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 最大正方形
     * @param matrix char字符型vector<vector<>>
     * @return int整型
     */
    //设dp[i][j]为以[i,j]为右下角的最大正方形面积
    //if(matrix[i][j]=='1'),min_area=min(dp[i-1][j-1]、dp[i-1][j]、dp[i][j-1])
    //dp[i][j]=min_area+square(min_area)*2+1
    int solve(vector<vector<char> >& matrix) {
        // write code here
        if (matrix.size() == 0) {
            return 0;
        } else if (matrix.size() == 1 && matrix[0][0] == '1') {
            return 1;
        } else if (matrix.size() == 1 && matrix[0][0] == '0') {
            return 0;
        }

        vector<vector<int>>dp(matrix.size(), vector<int>(matrix[0].size(), 0));
        int max_area = 0;
        for (int j = 0; j < matrix[0].size(); j++) {
            if (matrix[0][j] == '1') {
                dp[0][j] = 1;
                max_area = 1;
            } else {
                dp[0][j] = 0;
            }
        }
        for (int i = 0; i < matrix.size(); i++) {
            if (matrix[i][0] == '1') {
                dp[i][0] = 1;
                max_area = 1;
            } else {
                dp[i][0] = 0;
            }
        }
        for (int i = 1; i < matrix.size(); i++) {
            for (int j = 1; j < matrix[0].size(); j++) {
                if (matrix[i][j] == '1') {
                    int min_area = min(dp[i - 1][j - 1], dp[i - 1][j]);
                    min_area = min(min_area, dp[i][j - 1]);
                    dp[i][j] = min_area + sqrt(min_area) * 2 + 1;
                    max_area = max(max_area, dp[i][j]);
                }
                else {
                    dp[i][j]=0;
                }
            }
        }
        return max_area;
    }
};