221.最大正方形.cpp

/*
 * @lc app=leetcode.cn id=221 lang=cpp
 *
 * [221] 最大正方形
 */

// @lc code=start
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;
class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int m = matrix.size();
        if(m==0)return 0;
        int n = matrix[0].size();
        if(n==0)return 0;

        int maxSide = 0;
        vector<vector<int>> dp(m, vector<int>(n, 0));
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(matrix[i][j]=='1'){
                    if(i==0 || j==0)
                    {
                        dp[i][j] = 1;
                    }else{
                        dp[i][j] = min(dp[i-1][j], min(dp[i-1][j-1], dp[i][j-1])) + 1;
                    } 
                    maxSide = max(maxSide, dp[i][j]);
                }

            }
        }
        return maxSide * maxSide;
    }
};
// @lc code=end