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 <gene.ress...@gmail.com> 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 <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. > > -- 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.