In a square matrix, where each cell is black or white. Design an algorithm to find the maximum sub-square so that all 4 borders are black

Question

Given a square matrix, where each cell is black or white. Create an algorithm to find the maximum square so that all 4 borders are black.

I have an O (n ^ 2) algorithm:

Scan each column from left to right, for each cell in each column, scan each row to find the maximum sub-square with trailing edges.

Are there any better solutions?

thanks

Answer 1

O (n ^ 2). I think this is optimal since you have n ^ 2 cells.

Note that the upper left corner and lower right corner of any square lie along the same diagonal.

Now, if we could process each diagonal in O (n) time, we would have an O (n ^ 2) time algorithm.

Say we have a candidate for the upper left corner. We can calculate the number of continuous black cells below and to the right of it and take at least two of them and call it T.

For the lower right candidate, we can calculate the number of continuous black cells to his left, and at the top and take a minimum of two, call him.

Once we have two numbers T and B, we can tell if a given upper left, lower right candidate really gives us a square with all black borders.

Now these two numbers can be calculated for each cell O (n ^ 2) times by doing four passes over the entire matrix (How?).

So let's say this is done.

Now consider the diagonal. Our goal is to find the upper left lower right pair along this diagonal in O (n) time.

Suppose we have T computed in the array T [1 ... m], where m is the length of the diagonal. Similarly, we have an array B [1 ... m]. T [1] corresponds to the upper left edge of the diagonal and T [m] in the lower right corner. Similar to B.

Now we are processing the diagonal as follows, for each candidate to the upper left I am trying to find the lower right candidate j, which will give the largest square. Note that j> = i. Also note that if (i, j) is a candidate, then (i ', j) does not exist, where i'> i.

Note that i and j form a square if T[i] >= j-i+1 and B[j] >= j-i+1 .

i.e. T[i] +i - 1 >= j and B[j] -j - 1 >= -i .

So, we form new arrays such that TL[k] = T[k] + k -1 and BR[k] = B[k] -k - 1 .

So, given the two new arrays TL and BR and i, we need to answer the following queries:

What is the largest j such that TL [i]> = j and BR [j]> = -i?

Now suppose we were able to process BR for maximum range requests (this can be done in O (m) time).

Now, given TL [i], in the range [i, TL [i]] we find the maximum value of BR, for example, BR [j1].

Now, if BR [j1]> = -i, we find the maximum BR in the range [j1, TL [i]] and continue this path.

As soon as we find a candidate (TL [i], BR [j]), we can ignore the array BR [1 ... j] for future i.

This allows us to process each diagonal in O (n) time, giving a complete O (n ^ 2) algorithm.

I forgot a lot of details and gave a sketch, because it was already too long. Feel free to edit this with clarifications.

Phew

Answer 2

C ++ Code:

 #include<iostream> using namespace std; int min(int a,int b,int c) { int min = a; if(min > b) min = b; if(min > c) min = c; return min; } int main() { const int size = 5; char a[size][size] = { {'b','b','b','b','w'},{'b','b','b','b','b'},{'b','b','b','b','b'},{'b','b','w','b','b'},{'b','w','w','b','b'} }; int arr[size+1][size+1]; // First row and First column of arr is zero. for(int i=0;i<size+1;i++) { arr[0][i] = 0; arr[i][0] = 0; } int answer = 0; for(int i=0;i<size;i++) { for(int j=0;j<size;j++) { if(a[i][j] == 'w') arr[i+1][j+1] = 0; if(a[i][j] == 'b') { int minimum = min(arr[i][i],arr[i+1][j],arr[i][j+1]); arr[i+1][j+1] = minimum + 1; if( arr[i+1][j+1] > answer) answer = arr[i+1][j+1]; } } } for(int i=0;i<size+1;i++) { for(int j=0;j<size+1;j++) { cout<<arr[i][j]<<"\t"; } cout<<endl; } cout<<answer<<endl; return 0; } 

Answer 3

 /* In a square matrix, where each cell is black or white. * Design an algorithm to find the max sub-square such that all 4 borders are black. The right Java implementation based on a previous post. */ public int maxSubsquare(boolean[][] M){ int n = M.length; maxsize=0; checkDiag(M, 0, 0, n); for (int i=1; i<n; i++){ checkDiag(M, i, 0, n); checkDiag(M, 0, i, n); } return maxsize; } int maxsize; void checkDiag(boolean[][] M, int i, int j, int n){ if (i>=n-maxsize || j>=n-maxsize) return; int step = 0; while (step<(n-Math.max(i, j))&& M[i][j+step]&&M[i+step][j]){ int s = step; while (s>0){ if (M[i+s][j+step]&&M[i+step][j+s]) s--; else break; } if (s==0) maxsize = Math.max(maxsize, step+1); step++; } if (step==0) checkDiag(M, i+step+1, j+step+1, n); else checkDiag(M, i+step, j+step, n); } 

Answer 4

I do not know why you can get the O (n ^ 2) algorithm. Mathematically, this is not possible. Say you have an NxN matrix. You need to check: 1. 1 size matrix: NxN, 2. 2 * 2 size matrices: (N-1) x (N-1), 3. 3 * 3 size matrices: (N-2) x (N-2 ), ....

In general, you should check: 1+ 2 ^ 2 + 3 ^ 2 + ... + N ^ 2 = N (N + 1) (2N + 1) / 6. Thus, any algorithm cannot work better than O (N ^ 3)