Author |
Topic: Maximal Uni-Value Square (Read 909 times) |
|
Barukh
Uberpuzzler
Gender: 
Posts: 2276
|
 |
Maximal Uni-Value Square
« on: Feb 8th, 2007, 5:42am » |
 Quote  Modify
|
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? 
|
|
 IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Maximal Uni-Value Square
« Reply #1 on: Feb 8th, 2007, 5:53am » |
Quote Modify
|
The minor variation where all the sides had to be a given value (rather than either value) was posetd earlier 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
|
| « Last Edit: Feb 8th, 2007, 5:53am by SMQ » |
IP Logged |
--SMQ
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Maximal Uni-Value Square
« Reply #2 on: Feb 8th, 2007, 5:56am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Maximal Uni-Value Square
« Reply #3 on: Feb 8th, 2007, 5:56am » |
Quote Modify
|
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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Maximal Uni-Value Square
« Reply #4 on: Feb 11th, 2007, 9:32am » |
Quote Modify
|
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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
A
Full Member
Perder todas as esperanças é liberdade!
Gender:
Posts: 236
|
|
Re: Maximal Uni-Value Square
« Reply #5 on: Feb 12th, 2007, 12:36am » |
Quote Modify
|
Towr , can u give an example how ur algorithm works or Algorithm ?
your code is not obvious to me 
|
|
IP Logged |
What Doesn't Kill Me Will Only Make Me Stronger
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Maximal Uni-Value Square
« Reply #6 on: Feb 12th, 2007, 1:48am » |
Quote Modify
|
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.
|
| « Last Edit: Feb 12th, 2007, 1:55am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print