wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Maximal Uni-Value Square
        
(Message started by: Barukh on Feb 8^th, 2007, 5:42am)

Title: Maximal Uni-Value Square
Post by Barukh on Feb 8^th, 2007, 5:42am

Today, a friend of mine presented to me the following problem:

Given an MxN bit-matrix. Find the "largest square" in the matrix that has all the "sides" the same value (0 or 1).

Was this posted earlier? :-/

Title: Re: Maximal Uni-Value Square
Post by SMQ on Feb 8^th, 2007, 5:53am

The minor variation where all the sides had to be a given value (rather than either value) was posetd earlier (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1170284129) as one of a multi-question set, and in fact you replied to the thread, but no one has attempted to solve this problem.

--SMQ

Title: Re: Maximal Uni-Value Square
Post by Grimbal on Feb 8^th, 2007, 5:56am

Should the squares be straight? (i.e. with horizontal and vertical sides?).
Anyway, I don't see how to make it faster than the straightforward: try every pair as first side check that all 4 corners have the same state. The only optimization would in the way to enumerate the possible first sides in a way to avoid the other corners to lie outside of the rectangle.

Title: Re: Maximal Uni-Value Square
Post by towr on Feb 8^th, 2007, 5:56am

It is solvable in O(N*M) I think.. I had an idea how to do it, but I hadn't got round to working it out.
If I remember this time round, I'll post it later.

Title: Re: Maximal Uni-Value Square
Post by towr on Feb 11^th, 2007, 9:32am

Here's a simple algorithm, with worst case behaviour of O(min(N,M) * N * M ). But it should be quite a bit better on average.

Code:

foo(Mat[m][n])
{
tmp_v[m][n];
tmp_h[m][n];

// store how many succesive bits to the
// left are the same (exclusive)
for(x=0; x < m; x++)
{
tmp_v[x][n-1]=0;
for(y=n-2; y>=0; y--)
{
if(Mat[x][y] == Mat[x][y+1])
tmp_v[x][y] = tmp_v[x][y+1] + 1;
else
tmp_v[x][y] = 0;
}
}

// store how many succesive bits
// downwards are the same (exclusive)
for(y=0; y < n; y++)
{
tmp_h[m-1][y]=0;
for(x=m-2; x>=0; x--)
{
if(Mat[x][y] == Mat[x+1][y])
tmp_h[x][y] = tmp_h[x+1][y] + 1;
else
tmp_h[x][y] = 0;
}
}

// try squares, and check whether
// their sides are all the same value
curmax = curx = cury = 0;
if(m < n)
{
for(y=0; y < n; y++)
for(x=0; x < m; x++)
for(s=tmp_h[x][y]; s > curmax ; x2++)
if(tmp_v[x][y] >= s && tmp_v[x+s][y] >= s && tmp_h[x+s][y+s] >=s)
{
curmax = s;
curx=x;
cury=y;
}
}
else
{
for(x=0; x < m; x++)
for(y=0; y < n; y++)
for(s=tmp_v[x][y]; s > curmax ; x2++)
if(tmp_h[x][y] >= s && tmp_h[x][y+s] >= s && tmp_v[x+s][y+s] >=s)
{
curmax = s;
curx=x;
cury=y;
}
}

return [curx, cury, curmax+1];
}

It may very well still be improved upon.. Maybe a dynamic programming approach.

Title: Re: Maximal Uni-Value Square
Post by R0B1N on Feb 12^th, 2007, 12:36am

Towr , can u give an example how ur algorithm works or Algorithm ?

your code is not obvious to me :-[

Title: Re: Maximal Uni-Value Square
Post by towr on Feb 12^th, 2007, 1:48am

hmmm.. I had thought the comments in the code would be sufficient
But here's an example

starting with input matrix
1 0 0 1 1
1 0 0 1 0
0 1 1 1 0
0 1 1 1 1
1 1 1 1 1

First we create two more matrices, which records runlengths of a certain bit in a given direction (leftwards or downwards). so for example 11110 would become 32100, because from the first 1 we have 3 1s following it, the second 1 has 2 1s following, etc

So the horizontal scores
0 1 0 1 0
0 1 0 0 0
0 2 1 0 0
0 3 2 1 0
4 3 2 1 0

And vertical scores
1 1 1 4 0
0 0 0 3 1
1 2 2 2 0
0 1 1 1 1
0 0 0 0 0

Now we start looking at possible squares, if we take two corner (a, b) and (a, b+d) the other two corners are determined, because we're dealing with a square, so (a+d,b) and (a+d, b+d). if we look at (a,b) we know how often the value there is repeated, unless it is at least d times, the side to (a, b+d) doesn't have one value, and the same goes for (a, b) to (a+d, b) and (a+d, b) to (a+d, b+d).

Back to the example, our matrix is 5x5, so we're in the second part of the if-statement
We start at (0,0), our vertical scoring table give 1, so in the vertical direction we can make a sidelength with a maximum 2 pixels (assuming the matrix is a bitmap). However in the horizontal direction that won't work, because it's score is 0; so we are left with a 1x1 square at (0,0) (which our current maximum was already initialized to, and we never need to try smaller squares than our current maximum).
So next we try (0, 2), with the same result, in the vertical direction we can make a side of 2, but not in the horizontal one.
And then we get to (0,3) which is even worse, we can't get more than 1 vertically.
We increase x, and try (1,0). There, we get vertically a side of 2 and horizontally also. This means we can get to (1,1) and (2,0). So we need to check if we can get to (2,1). And if we check the vertical score for (2,0) that checks out, and the horizontal score for (1,1) also. So we now have a 2x2 square as our current maximum.
Our next attempt at forming a square starts at (1,3), vertically we can make a side of length 3, horizontally also, and from those new corners, (3,3) and (1,5) , we can also get to the last one (3,5).

And from this point onward we can't get a bigger square, because we already passed the points where a 4x4 square could possibly start, but I didn't put that check in the algorithm.