[LeedCode OJ]#221 Maximal Square

 【 聲明：版權所有，轉載請标明出處，請勿用于商業用途。  聯系信箱：[email protected]】

題目連結：https://leetcode.com/problems/maximal-square/

題意： 給出一個隻包含0,1的二維矩陣，要求找到一個全為1的正方形的子矩陣，并輸出子矩陣的面積

思路： 詳細解釋請參考Maximal Rectangle，在這裡隻需要增加一個判斷即可，那就是r==c

class Solution
{
public:
    int maximalSquare(vector<vector<char>>& matrix)
    {
        int n = matrix.size();
        if(n==0) return 0;
        int m = matrix[0].size();
        int i,j,c;
        vector<vector<int> > dp,a;
        dp.resize(n+1),a.resize(n+1);
        for(i = 0; i<=n; i++)
        {
            dp[i].resize(m+1);
            a[i].resize(m+1);
        }
        for(i = 0; i<n; i++)
        {
            for(j = 0; j<m; j++)
            {
                a[i+1][j+1] = matrix[i][j]-'0';
            }
        }
        int sum = 0;
        for(i = 1; i<=m; i++)
        {
            sum+=a[1][i];
            dp[1][i] = sum;
        }
        for(i = 2; i<=n; i++)
        {
            sum = 0;
            for(j = 1; j<=m; j++)
            {
                sum+=a[i][j];
                dp[i][j]=dp[i-1][j]+sum;
            }
        }
        int maxn = 0;
        for(i = n; i>0; i--)
        {
            for(j = m; j>0&&maxn<i*j; j--)
            {
                if(a[i][j])
                {
                    int r = 1,c = 1;
                    while(j-c>=0)
                    {
                        if(dp[i][j]-dp[i][j-c]-dp[i-r][j]+dp[i-r][j-c]==r*c)
                        {
                            if(r==c)
                                maxn = max(maxn,r*c);
                            c++;
                        }
                        else
                            break;
                    }
                    while(i-r>=0&&c>0)
                    {
                        if(dp[i][j]-dp[i][j-c]-dp[i-r][j]+dp[i-r][j-c]==r*c)
                        {
                            if(r==c)
                                maxn = max(maxn,r*c);
                            r++;
                        }
                        else
                            c--;
                    }
                }
            }
        }
        return maxn;
    }
};