@jalaj: sorry for delay i was busy these days
the implementation of my method is a bit hard because R2 and R4 which i
mentioned before are not always squares
and in that case we must first break the rectangles into squares and then
perform the search on squares
here breakToSquares function breaks a rectangle to min number of squares and
returns true if x was in one of them
bool rec(int x,int sti,int stj,int n,int m){
//x is what we're searching for. sti and stj show the starting point of the
matrix. m and n show the size
if (m==1 && n==1){
if (a[sti][stj]==x)
return true;
else
return false;
}
if (m==0 || n==0)
return false;
if (n!=m)
return breakToSquares(x,sti,stj,m,n);
firsti=sti;
firstj=stj;
lasti=sti+n;
lastj=stj+m;
while (firsti<lasti && firstj<lastj){ // binsearch loop
i=(firsti+lasti)/2;
j=(firstj+lastj)/2;
if (a[i][j]==x)
return true;
if (a[i][j]<x && a[i+1][j+1]>x)
break;
if (a[i+1][j+1]<x){
firsti=i+1;
firstj=j+1;
}
if (x<a[i][j]){
lasti=i;
lastj=j;
}
}
if (rec(i,stj,n-i,j+1) || rec(sti,j,i+1,m-j))
return true;
return false;
}
--
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.
