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].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
