asnwer to original question....i have not checked it yet, apologies in case
of some mistake...
int t[n+1][n+1];
for (int i=0;i<=n;i++)
t[i][0]=0;
for (int j=0;j<=n;j++)
t[0][j]=0;
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
if (t[i-1][j] && (t[i-1][j] == t[i][j-1]))
{
t[i][j]=t[i-1][j-1]+1;
if ( maxL < t[i][j]) {maxL=t[i][j]; rightBottomX=i;
rightBottomY=j;}
}
else t[i][j]=0;
Best Regards
Ashish Goel
"Think positive and find fuel in failure"
+919985813081
+919966006652
On Wed, Oct 27, 2010 at 11:30 AM, rahul patil <[email protected]
> wrote:
> hello all,
>
> suppose given matrix contains the 0(white) and 1(black)
>
> 00000
> 11100
> 00100
> 11100
> 01100
>
> create the matrix R as follows
> 1> traverse each row where each cell represents no of continuos balck cells
> till the current cell
>
> 00000
> 12300
> 00100
> 12300
> 01200
>
> similarly
> creat the matrix C as follows
> 1> traverse each column where each cell represents no of continuos balck
> cells till the current cell
>
> 00000
> 11100
> 00200
> 11300
> 02400
>
> Now it is easy job
>
> 1> traverse matrix row wise ( matrix is n,n )
> 2> go to position i,j i=row j=column
> 3> if R(i,j) > 1 , then go till k,j (where i < k <= n )
> for every (k=n;k>i;k--)
> if R(k,j) > abs(i-k) {
> if C(k,j) >= abs(i-k) && C(k- abs(i-k)>= abs(i-k) {
> if(abs(i-k) < max_side){
> maxi = i
> maxj = k;
> max_side = abs(i-k)
> }
> }
>
> 4> sol is square of length max_side with upper right corner maxi,maxj
>
>
>
>
>
>
>
> On Fri, Oct 15, 2010 at 9:24 PM, snehal jain <[email protected]>wrote:
>
>> Imagine you have a square matrix, where each cell is filled with
>> either black or white. Design an algorithm to find the maximum
>> subsquare such that all four borders are filled with black pixels.
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to [email protected].
>> To unsubscribe from this group, send email to
>> [email protected]<algogeeks%[email protected]>
>> .
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>>
>
>
> --
> Regards,
> Rahul Patil
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to
> [email protected]<algogeeks%[email protected]>
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
