题解 | #最大正方形#

#include <algorithm>
#include <vector>
class Solution {
  public:

    int solve(vector<vector<char> >& matrix) {
        // 初始时对第一列和第一行进行赋值后，之后依次遍历，
        //当遇到为0的则仍然为0，当遇到为1，则比较对角和当前元素的该列和该行
        int n = matrix.size();//表示lie
        int m = matrix[0].size();//表示行
        if(n == 0) return 0;
        vector<vector<int>> dp(n, vector<int>(m));
        for (int i = 0; i < n; i++) dp[i][0] = (matrix[i][0] - '0');
        for (int i = 0; i < m; i++) dp[0][i] = (matrix[0][i] - '0');
        int maxlen = 0;
        for (int i = 1; i < n; i ++) {
            for (int j = 1; j < m; j++) {
                if (matrix[i][j] == '0') dp[i][j] = 0;
                else {
                   dp[i][j] = min(dp[i- 1][j - 1], min(dp[i -1][j], dp[i][j - 1])) + 1;
                }
                maxlen = max(dp[i][j], maxlen);
            }

        }
        return maxlen * maxlen;
    }
};