[algogeeks] Re: Maximize Subsquare
allOnes(row, column, len) so allone(i, 0, k) will check if A[i][0] to A[i][k] has all the ones similarly another allone should check for all column values. so algo is "if you come across any i, j which is '1' , then check for sq ending at i-1, j-1 and all the borders , if all are ones, store the length of sq at A[i][j]" On Nov 26, 3:44 pm, tech coder wrote: > @ Chunyuan Ge > *have u checked ur solution . ur solution is to find the submatrix all > filled with 1 , but the question say that 1 can be at boundaries. > * > On Wed, Nov 23, 2011 at 3:00 PM, kumar raja wrote: > > > > > > > > > > > @Dark prince : what is meant by Allones(i,0.k) what subsquare he is > > considering here?? > > > On 22 November 2011 23:57, DarkPrince wrote: > > >> It means that the Borders of the mavximum rectangle should hav all 1s > >> irrespective the elements inside the rectangles , it can be either 0 > >> or 1 . > > >> -- > >> 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. > > > -- > > Regards > > Kumar Raja > > M.Tech(SIT) > > IIT Kharagpur, > > 10it60...@iitkgp.ac.in > > > -- > > 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. > > -- > * > > Regards* > *"The Coder"* > > *"Life is a Game. The more u play, the more u win, the more u win , the > more successfully u play"* -- 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.
Re: [algogeeks] Re: Maximize Subsquare
@ Chunyuan Ge *have u checked ur solution . ur solution is to find the submatrix all filled with 1 , but the question say that 1 can be at boundaries. * On Wed, Nov 23, 2011 at 3:00 PM, kumar raja wrote: > @Dark prince : what is meant by Allones(i,0.k) what subsquare he is > considering here?? > > > On 22 November 2011 23:57, DarkPrince wrote: > >> It means that the Borders of the mavximum rectangle should hav all 1s >> irrespective the elements inside the rectangles , it can be either 0 >> or 1 . >> >> -- >> 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. >> >> > > > -- > Regards > Kumar Raja > M.Tech(SIT) > IIT Kharagpur, > 10it60...@iitkgp.ac.in > > > -- > 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. > -- * Regards* *"The Coder"* *"Life is a Game. The more u play, the more u win, the more u win , the more successfully u play"* -- 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.
Re: [algogeeks] Re: Maximize Subsquare
@Dark prince : what is meant by Allones(i,0.k) what subsquare he is considering here?? On 22 November 2011 23:57, DarkPrince wrote: > It means that the Borders of the mavximum rectangle should hav all 1s > irrespective the elements inside the rectangles , it can be either 0 > or 1 . > > -- > 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. > > -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- 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.
[algogeeks] Re: Maximize Subsquare
It means that the Borders of the mavximum rectangle should hav all 1s irrespective the elements inside the rectangles , it can be either 0 or 1 . -- 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.
[algogeeks] Re: Maximize Subsquare
It means that the Borders of the mavximum rectangle should hav all 1s irrespective the elements inside the rectangles , it can be either 0 or 1 . -- 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.
Re: [algogeeks] Re: Maximize Subsquare
@Vikas : what is the meaning of Allones function??
On 8 November 2011 15:13, Chunyuan Ge wrote:
> Say you define ur matrix in M
>
> then
>
> if (M(i,j) = 1)
> Sq(i,j) = min(Sq(i-1,j),Sq(i-1,j-1),Sq(i, j-1)) + 1
> else
> Sq(i,j) = 0
>
>
>
>
>
> On Tue, Nov 8, 2011 at 7:27 AM, vikas wrote:
>
>> try this:
>> sq(i, j)= k is maximum sqare possible ending at i, j and has
>> length k in the matrix iXj
>>
>>sq(i, j) = k if {sq( i -1, j-1) && AllOnes(i,0,
>> k) && AllOnes(0, j, k)}
>> = 1 if sq(i, j) == 1
>> = 0 otherwise
>>
>>
>> On Oct 31, 10:36 pm, SAMM wrote:
>> > Any body got any idea of just how to approach It need a DP algo.
>> >
>> > On 10/30/11, SAMMM wrote:
>> >
>> >
>> >
>> > > Suppose u have a square matrix, where every cell is filled with 0 or
>> > > 1 . U need to find the maximum subsquare such that all four borders
>> > > are filled with all 1s.
>> >
>> > > Ex:-
>> >
>> > > 1 0 0 1 1 0
>> > > 1 0 1 1 1 0
>> > > 0 0 1 0 1 1
>> > > 0 1 1 1 1 0
>> > > 1 0 0 1 1 1
>> >
>> > > Here the maximum square (3X3) possible is from the TOP LEFT (2 3) TO
>> > > BOTTOM RIGHT (4 5) .
>> >
>> > > --
>> > > 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.
>> >
>> > --
>> > Somnath Singh
>>
>> --
>> 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.
>
--
Regards
Kumar Raja
M.Tech(SIT)
IIT Kharagpur,
10it60...@iitkgp.ac.in
--
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.
Re: [algogeeks] Re: Maximize Subsquare
Say you define ur matrix in M
then
if (M(i,j) = 1)
Sq(i,j) = min(Sq(i-1,j),Sq(i-1,j-1),Sq(i, j-1)) + 1
else
Sq(i,j) = 0
On Tue, Nov 8, 2011 at 7:27 AM, vikas wrote:
> try this:
> sq(i, j)= k is maximum sqare possible ending at i, j and has
> length k in the matrix iXj
>
>sq(i, j) = k if {sq( i -1, j-1) && AllOnes(i,0,
> k) && AllOnes(0, j, k)}
> = 1 if sq(i, j) == 1
> = 0 otherwise
>
>
> On Oct 31, 10:36 pm, SAMM wrote:
> > Any body got any idea of just how to approach It need a DP algo.
> >
> > On 10/30/11, SAMMM wrote:
> >
> >
> >
> > > Suppose u have a square matrix, where every cell is filled with 0 or
> > > 1 . U need to find the maximum subsquare such that all four borders
> > > are filled with all 1s.
> >
> > > Ex:-
> >
> > > 1 0 0 1 1 0
> > > 1 0 1 1 1 0
> > > 0 0 1 0 1 1
> > > 0 1 1 1 1 0
> > > 1 0 0 1 1 1
> >
> > > Here the maximum square (3X3) possible is from the TOP LEFT (2 3) TO
> > > BOTTOM RIGHT (4 5) .
> >
> > > --
> > > 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.
> >
> > --
> > Somnath Singh
>
> --
> 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.
[algogeeks] Re: Maximize Subsquare
try this:
sq(i, j)= k is maximum sqare possible ending at i, j and has
length k in the matrix iXj
sq(i, j) = k if {sq( i -1, j-1) && AllOnes(i,0,
k) && AllOnes(0, j, k)}
= 1 if sq(i, j) == 1
= 0 otherwise
On Oct 31, 10:36 pm, SAMM wrote:
> Any body got any idea of just how to approach It need a DP algo.
>
> On 10/30/11, SAMMM wrote:
>
>
>
> > Suppose u have a square matrix, where every cell is filled with 0 or
> > 1 . U need to find the maximum subsquare such that all four borders
> > are filled with all 1s.
>
> > Ex:-
>
> > 1 0 0 1 1 0
> > 1 0 1 1 1 0
> > 0 0 1 0 1 1
> > 0 1 1 1 1 0
> > 1 0 0 1 1 1
>
> > Here the maximum square (3X3) possible is from the TOP LEFT (2 3) TO
> > BOTTOM RIGHT (4 5) .
>
> > --
> > 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.
>
> --
> Somnath Singh
--
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.
