a***e
发帖数: 413 | 1 这样是不是 O(N^N)的复杂度?
class Solution {
public:
int maximalRectangle(vector > &matrix) {
int row=matrix.size();
if (row==0) return 0;
int col=matrix[0].size();
if (col==0) return 0;
//find all disjoint rectangles
vector> flag(row, vector(col,false));
int maxArea=INT_MIN;
for (int r=0; r
for (int c=0; c
{
int area=0;
if (matrix[r][c]=='1'&&flag[r][c]==false)
{
area+=helper(matrix,r,c,flag, row, col);
}
maxArea=max(maxArea,area);
}
return maxArea;
}
int helper(vector> &m, int r, int c, vector> f
, int row, int col)
{
if (r
{
if (f[r][c]=false&&m[r][c]=='1')
f[r][c]=true;
if (r+1
{
f[r+1][c]=true;
return (2+helper(m,r+2,c,f,row,col));
}
if (c+1
{
f[r][c+1]=true;
return (2+helper(m,r,c+2,f,row,col));
}
return 1;
}
else
return 0;
}
}; |
|
