@rahul
may be this will help you..
/* Given a binary matrix, find out the maximum size square sub-matrix with
all 1s.
1. O(n^3) sol is very obvious
2. O(n^2) sol [ this file]
3. O(n) sol [ possible but we need to know tucker matrix, etc advanced
set theory's]
*/
#include<iostream>
#include<conio.h>
int b[6][6];
using namespace std;
main()
{ int i,j,t;
int a[6][6]=
{ 0,0,0,1,0,1,
0,1,1,1,0,0,
1,1,1,1,0,1,
0,1,1,1,1,0,
1,0,0,1,0,0,
0,1,0,1,1,0,};
for(i=0;i<6;i++)
for(j=0;j<6;j++)
{ if(a[i][j]==1)
{
b[i][j]=min(min(b[i-1][j],b[i][j-1]),b[j-1][i-1])+1;
}
else
b[i][j]=0;
}
for(i=0;i<6;i++)
{ for(j=0;j<6;j++)
{ printf(" %d",a[i][j]);
}
printf("\n");
}
printf("\n\n\n\n\n");
for(i=0;i<6;i++)
{ for(j=0;j<6;j++)
{ printf(" %d",b[i][j]);
}
printf("\n");
}
getch();
return 0;
}
On Wed, Mar 14, 2012 at 11:56 AM, Sourabh Singh <[email protected]>wrote:
> @atul
>
> 1) it won't work for large dimention's coz their is a limit to size of
> array we can declare on stack.
> ( which is typically 10^6 as far as i know :-) ).
>
> 2) the algo i m trying to find would work in linear time. while this one
> is more then O(n^2)
> fo rvery very large input this algo would be very very slow.. making
> it impractial..
>
> ( it's like if u can find substring's in linear time then why use an
> O(n^2) algo ;-) )
>
> NOTE: sry if m getting any fact's wrong m in mid of exam's (so a bit short
> on time to check implemention of your algo right now )
>
>
>
> On Wed, Mar 14, 2012 at 9:07 AM, atul anand <[email protected]>wrote:
>
>> @rahul: i have alreday explained it in the provided link.
>> @sourbh : why it would not work for large dimension
>> On 14 Mar 2012 19:39, "rahul sharma" <[email protected]> wrote:
>>
>>> @atul..plz tell me an example for square matrix...actually i faced it
>>> first tym...it executes...but explain plz..
>>>
>>> On Wed, Mar 14, 2012 at 6:56 PM, Sourabh Singh <[email protected]
>>> > wrote:
>>>
>>>> @atul
>>>>
>>>> Also the histogram algo and algo given by you can't work on very very
>>>> big dimentions. say 10^5 x 10^5 matrix.
>>>> but if we can find a DP then we just need to keep 2 row's at a time.
>>>> :-)
>>>>
>>>>
>>>>
>>>> On Tue, Mar 13, 2012 at 1:03 PM, Sourabh Singh <
>>>> [email protected]> wrote:
>>>>
>>>>> @atul
>>>>>
>>>>> read it ..
>>>>>
>>>>> it's good but more or less like the histogram algo.. i wanted a DP.
>>>>> approach..
>>>>>
>>>>> here is some of wat i heard from a senior in colg..
>>>>>
>>>>> 1. at every index we can keep 4 variable
>>>>>
>>>>> ht: height of max rectangle possible at index above current
>>>>> wt width " " " " "
>>>>> " "
>>>>> hl:height of max rectangle possible at index left of current
>>>>> wl: " " " " "
>>>>> " "
>>>>>
>>>>>
>>>>> now problem is which one to take for current... index
>>>>>
>>>>>
>>>>>
>>>>> On Tue, Mar 13, 2012 at 10:52 AM, atul anand
>>>>> <[email protected]>wrote:
>>>>>
>>>>>> @ Sourabh: check solution i have posted in below link
>>>>>>
>>>>>>
>>>>>> http://groups.google.com/group/algogeeks/browse_thread/thread/91a17f7c78c2319e/991d1c2625a62ff0?hl=en&lnk=gst&q=rectangle+of+max+sum+MS+Q#991d1c2625a62ff0
>>>>>>
>>>>>>
>>>>>>
>>>>>> On Tue, Mar 13, 2012 at 10:26 PM, Sourabh Singh <
>>>>>> [email protected]> wrote:
>>>>>>
>>>>>>> @ ALL
>>>>>>>
>>>>>>> finding square matrix is quite a standard question and nw an easy
>>>>>>> one as everyone knows the reccussence atul has given.
>>>>>>> but i wanted to find max rectangle..
>>>>>>>
>>>>>>> i know there is a DP for it. in O(n^2). for nxn matrix..don't know
>>>>>>> the whole approach .but here is what i remember..
>>>>>>>
>>>>>>> 1. aproach is simple to keep track of max rectangle which can be
>>>>>>> formed from any point taking that point as top left corner of max
>>>>>>> rectangle and
>>>>>>> proceed further down .
>>>>>>>
>>>>>>> can someone suggest how can be proceed further..
>>>>>>>
>>>>>>>
>>>>>>> [ NOTE: problem occurs mainly when their are more than one
>>>>>>> rectangles which can be formed from same point ]
>>>>>>>
>>>>>>> plz.. don't suggest the histogram method it's just a dirty way of
>>>>>>> avoiding to work on getting this DP right. :-)
>>>>>>>
>>>>>>>
>>>>>>> On Mon, Mar 12, 2012 at 11:29 PM, atul anand <
>>>>>>> [email protected]> wrote:
>>>>>>>
>>>>>>>> here is the recurrence for solving this
>>>>>>>>
>>>>>>>> R[i, j] = (M[i,j] == 0 ? 0 : 1 + min( R[i-1, j], R[i-1, j-1],
>>>>>>>> R[i,,j-1] ) );
>>>>>>>>
>>>>>>>>
>>>>>>>> On Tue, Mar 13, 2012 at 11:48 AM, rahul sharma <
>>>>>>>> [email protected]> wrote:
>>>>>>>>
>>>>>>>>>
>>>>>>>>> April 4, 2010
>>>>>>>>>
>>>>>>>>> Given a binary matrix, find out the maximum size square sub-matrix
>>>>>>>>> with all 1s.
>>>>>>>>>
>>>>>>>>> For example, consider the below binary matrix.
>>>>>>>>>
>>>>>>>>> 0 1 1 0 1
>>>>>>>>> 1 1 0 1 0
>>>>>>>>> 0 1 1 1 0
>>>>>>>>> 1 1 1 1 0
>>>>>>>>> 1 1 1 1 1
>>>>>>>>> 0 0 0 0 0
>>>>>>>>>
>>>>>>>>> The maximum square sub-matrix with all set bits is
>>>>>>>>>
>>>>>>>>> 1 1 1
>>>>>>>>> 1 1 1
>>>>>>>>> 1 1 1
>>>>>>>>>
>>>>>>>>> --
>>>>>>>>> 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.
>>>>>>
>>>>>
>>>>>
>>>> --
>>>> 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.
