int countRight[n][n];
int countDown[n][n];
int i,j,s;
int bestI, bestJ, max=0;
int lastRight = n;
int lastDown = n;
// Start by setting countRight[i][j] to the number of consecutive
black pixels starting at (i,j) and moving right
// and countDown[i][j] to the number of consecutive black pixels
starting at (i,j) and moving down
for(i = 0; i < n; ++i)
for(j = n-1; j >= 0; --j)
{
if (m[i][j] == white) lastRight = j;
if (m[j][i] == white) lastDown = j;
countRight[i][j] = lastRight - j;
countDown[j][i] = lastDown - j;
}
// Now look for largest square with top left corner at (i,j)
for(i = 0; (i+max) < n; ++i)
for(j = 0; (j+max) < n; ++j)
for(s = Min(countRight[i][j], countDown[i][j]); s > max; --s)
if ((countRight[i+s][j] >= s) && (countDown[i][j+s] >= s))
{
bestI = i; bestJ = j; max = s;
}
Don
On Jan 16, 2:08 pm, marti <[email protected]> wrote:
> Imagine there is a square matrix with n x n cells. Each cell is either
> filled with a black pixel or a white pixel. Design an algorithm to find the
> maximum subsquare such that all four borders are filled with black pixels;
> optimize the algorithm as much as possible
--
