Maximal Square(dp,cpp,leetcode)
Maximal Square (dp,cpp,leetcode)
Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.
Example:
Input: 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0 Output: 4
problem link====== https://leetcode.com/problems/maximal-square/
==========================================================================================
class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix)
{
int maxm=0;
if(matrix.size()==0)
return 0;
int t[matrix.size()][matrix[0].size()];
memset(t,0,sizeof(t));
for(int i=0;i<matrix.size();i++)
{
t[i][0]=matrix[i][0]-48;
if(maxm<t[i][0])
maxm=t[i][0];
}
for(int i=0;i<matrix[0].size();i++)
{
t[0][i]=matrix[0][i]-48;
if(maxm<t[0][i])
maxm=t[0][i];
}
for(int i=1;i<matrix.size();i++)
{
for(int j=1;j<matrix[0].size();j++)
{
if(matrix[i][j]=='1')
{
t[i][j]= 1+ min( t[i-1][j-1], min(t[i-1][j],t[i][j-1]) );
// maxm=max(maxm,t[i][j]);
if(maxm<t[i][j])
maxm=t[i][j];
}
}
}
return maxm*maxm;
}
};
Comments
Post a Comment