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: 
 
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

Popular posts from this blog

Amazing Subarrays(cpp,interviewbit)

Symmetric Tree(leetcode,cpp):

sum of left leaves in a tree(leetcode).