g[][]- given matrix
r[][]- result matrix
copy first row n column from g[][] to r[][]
rest
for i=1 to n-1
for =1 to n-1j
if(g[][])
r[][]=min(r[i][j-1],r[i-1][j],r[i-1][j-1])+1;
else
r[][]=0;
On Wed, Jan 11, 2012 at 10:00 AM, Gene <[email protected]> wrote:
> 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 <[email protected]> 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 <[email protected]>
> 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 <[email protected]
> >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 [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.
> >
> > > --
> > > 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.
>
> --
> 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.
>
>
--
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.
