88最大正方形(221)

作者: Turbo时间限制: 1S章节: 动态规划

晚于: 2020-09-02 12:00:00后提交分数乘系数50%

截止日期: 2020-09-09 12:00:00

问题描述 :

在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。

示例:

输入: 

1 0 1 0 0

1 0 1 1 1

1 1 1 1 1

1 0 0 1 0

输出: 4

输入说明 :

首先输入矩阵的行数m、列数n

然后输入m行，每行n个字符0或1，中间无空格分隔。

输出说明 :

输出一个整数

输入范例 :

4 5 10100 10111 11111 10010

输出范例 :

4

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int maximalSquare(vector<vector<int>>& matrix) 
    {
        if(matrix.size()==0)
            return 0;
        int m=matrix.size(),n=matrix[0].size();
        vector<vector<int>> dp(m,vector<int>(n));
        int len=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(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
                }
                len=max(len,dp[i][j]);
            }
        }
        return len*len;
    }
};
int main()
{
    int m, n;
    char data;
    vector<vector<int> > matrix;
    cin>>m>>n;
    for(int i=0; i<m; i++)
    {
        vector<int> row;
        for(int j=0; j<n; j++)
        {
            cin>>data;
            row.push_back(data-'0');
        }
        matrix.push_back(row);
    }
    int res=Solution().maximalSquare(matrix);
    cout<<res<<endl;
    return 0;
}