The 1's and 0's are in matrix R. We want to compute an integer matrix
M of the same dimensions as R such that Mij is the size of the largest
square of 1's of which Rij is the bottom right corner. As we go we
can keep track of max(Mij), and this will be the answer.
So how to compute Mij? The values north, west, and northwest of Mij
tells us about the sizes of squares of 1's in those directions. If we
take the min; call it M, then we can be sure all the elements of the
square with diagonal (i,j)->(i-M,j-M) are all 1's and moreover that if
we tried a bigger square we'd either run off the edge of the matrix or
hit a zero. So the size of this new square is M+1.
Atul anand's algorithm is almost the story. He left out the base
cases. The left and top edges of M are just the same as R. So to
write a program,
for (i = 0; i < m; i++)
for (j = 0; j < n; j++)
M[i][j] = (i == 0 || j == 0 || R[i][j] == 0) ? R[i][j] :
1 + min3(M[i-1][j], M[i-1,j-1], M[i][j-1]);
If you recode this carefully, you don't need a 2d matrix for M. You
can get away with a single row plus one integer variable.
On Jan 10, 11:37 am, Sanjay Rajpal <sanjay.raj...@live.in> wrote:
> Its a square matrix containing 0s and 1s.
>
> Will u plz elaborate about this equation ?
> *
> Sanjay Kumar
> B.Tech Final Year
> Department of Computer Engineering
> National Institute of Technology Kurukshetra
> Kurukshetra - 136119
> Haryana, India
> Contact: +91-8053566286
> *
>
>
>
>
>
>
>
> On Tue, Jan 10, 2012 at 8:36 AM, atul anand <atul.87fri...@gmail.com> wrote:
> > i dint get...you should provide more details , if it is all 1 then whole
> > matrix is a max square..
>
> > anyways equation to find max sub square is this.
>
> > M[i,j]=R[i,j]==0 ? 0 : 1+min(M[i-1][,j] , M[i][j-1], M[i-1][j-1] )
>
> > On Tue, Jan 10, 2012 at 10:00 PM, Sanjay Rajpal
> > <sanjay.raj...@live.in>wrote:
>
> >> Suggest an algorithm guyzzz.....
>
> >> *
> >> Sanjay Kumar
> >> B.Tech Final Year
> >> Department of Computer Engineering
> >> National Institute of Technology Kurukshetra
> >> Kurukshetra - 136119
> >> Haryana, India
> >> Contact: +91-8053566286
> >> *
>
> >> --
> >> You received this message because you are subscribed to the Google Groups
> >> "Algorithm Geeks" group.
> >> To post to this group, send email to algogeeks@googlegroups.com.
> >> To unsubscribe from this group, send email to
> >> algogeeks+unsubscr...@googlegroups.com.
> >> 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 algogeeks@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com.
> > 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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
