Here is the complete program ..
First create a square matrix Y for which
Y[i][j] represents number of contiguous 1's till row i in the column j of
matrix A ,which is the source matrix.
Now let i and j be two levels at which our matrix of maximum size is
contained.For each column of the matrix contained between level i and j we
calculate if it contains all 1's or not using matrix Y (in O(1) ). If yes
add the number of 1's to a variable count and proceed to the next column and
repeat the procedure .If at any point a column does not contains all 1's
then we set count to zero .Thus at the end of one iteration between levels i
and j we will have maximum number of contiguous 1's between level i and j
.Then we can check if these are contained in a square matrix or not.This is
illustrated in the program.
1 0 0 1 1 1
1 1 0 1 1 0
i----> 1 0 1 1 1 1
1 1 1 1 1 1
j----> 1 0 1 1 1 0
1 1 1 0 1 1
#include <vector>
#include <iostream>
#define FOR(i,k,n) for(int i=k;i<n;i++)
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
struct Points
{
int x;
int y;
};
int main()
{
Points top,bottom;
int n;
cin>>n;
vvi A(n,vi(n,0));
vvi Y(n,vi(n,0));
FOR(i,0,n)
FOR(j,0,n)
cin>>A[i][j];
FOR(i,0,n)
Y[0][i]=A[0][i];
FOR(i,1,n)
FOR(j,0,n)
if(A[i][j])
Y[i][j]=Y[i-1][j]+1;
int count=0,c=0,max=0,prev=0;
FOR(i,0,n)
FOR(j,i+1,n)
{
count=0;
prev=0;
FOR(k,0,n)
{
if(i!=0)
c=Y[j][k]-Y[i-1][k];
else
c=Y[j][k];
if(c==j-i+1 )
count=count+(j-i+1);
else
{
prev=k+1;
count=0;
}
if(count>max && j-i==k-prev) //second condition is check for square
matrix
{
top.x=i;
top.y=prev;
bottom.y=k;
bottom.x=j;
max=count;
}
}
}
cout<<"Top left: ("<<top.x<<","<<top.y<<")\nBottom Right:
("<<bottom.x<<","<<bottom.y<<")"<<endl<<"Total number of 1's : "<<max;
}
Mukesh Gupta
Delhi College of Engineering
On Mon, Oct 4, 2010 at 11:23 PM, Chi <c...@linuxdna.com> wrote:
> Maybe you meant this: Multidimensional Range Search in Dynamically
> Balanced Trees.
>
> > http://www.vision-tools.com/h-tropf/multidimensionalrangequery.pdf
>
> There is surely a better way, but a Z-Curve traversal is like a
> quadtree, or spatial index of 2-dimensional data, or binary matrix.
> You can calculate the "Bigmin".
>
>
> On Oct 4, 5:25 pm, mac adobe <macatad...@gmail.com> wrote:
> > @chi .. can you please share what is this and how it resolves the issue
> at
> > hand ?
> >
> > regards
> > --mac
> >
> >
> >
> > On Mon, Oct 4, 2010 at 5:50 PM, Chi <c...@linuxdna.com> wrote:
> > > Traverse the matrix in z-order, or hilbert-order. This is a heuristic-
> > > algo.
> >
> > > On Oct 4, 1:51 pm, mac adobe <macatad...@gmail.com> wrote:
> > > > 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
> >
> > > > then a 3x3 1 matrix eists
> >
> > > > the second question is .. if such a matrix (square matrix does not
> > > > exist) find one with maximum 1s .
> >
> > > > --
> > > > thanks
> > > > --mac
> >
> > > --
> > > You received this message because you are subscribed to the Google
> Groups
> > > "Algorithm Geeks" group.
> > > To post to this group, send email to algoge...@googlegroups.com.
> > > To unsubscribe from this group, send email to
> > > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> <algogeeks%2bunsubscr...@googlegroups.com<algogeeks%252bunsubscr...@googlegroups.com>
> >
> > > .
> > > For more options, visit this group at
> > >http://groups.google.com/group/algogeeks?hl=en.
> >
> > --
> > thanks
> > --mac
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@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 algoge...@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.
