Question

每一个囚室都是黑白的,有固定的矩阵。设计一种算法,以找到最大分局,这样所有4个边界都是黑色的。

我有O(n^2)算法:

每一栏每个栏目从左到右边的栏目,每个栏目每个栏目扫描每一行,以找到带后边界的顶部。

是否有更好的解决办法?

thanks

Answer 1

O(n^2) is possible. I guess it is optimal, as you have n^2 cells.

通知说,任何广场的顶端角和底层右角位于同一寺。

现在,如果我们能够在奥(n)时间处理每一分校,我们就会有奥(n^2)时间算法。

Say we have a candidate for a top-left corner. We can compute the number of continuous black cells below it, and to the right of it and take the minimum of the two and call it T.

对于一位底层候选人,我们可以将连续的黑囚房数量与左边和顶上调,并将这两间牢房的最低点称为B。

Once we have the two numbers T and B, we can tell if the given top-left, bottom-right candidate actually give us a square with all black borders.

现在,这两个数字可以通过通过整个矩阵(How?)来计算,在O(n^2)时间计算。

因此,让我们假设这样做。

Now consider a diagonal. Our aim is to find a top-left,bottom-right pair along this diagonal in O(n) time.

让我们假设的是,在“......m”号阵列中,“T”号是“神学”的长度。同样,我们有阵列B[1.m]。 T 3.1 相当于离校和T[m]最左端。同样与B。

现在,我们处理以下各点,即每个高位候选人,我们试图找到一个将给予最大面积的底层候选人。通知:j > i 并且注意到,如果(i,j)是候选人,则(i,j)是nt, 即i >

请注意,i和j如果是T[i] >=j-i+1和B[j] >=j-i+1,则构成一平方米。

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

因此,我们形成了新的阵列,例如TL[k] = T[k] + k <-1>和BR[k] = B[k] -k - 1。



因此,鉴于TL和BR这两个新阵列,以及一,我们需要回答以下问题:


  TL[i] >=j and BR[j] >=i?


如今,我们已经能够处理大范围询问的BR(可在O(m)时间处理)。

现在给了TL[i],在[i, TL[i]范围内,我们发现BR的最大价值,例如BR[j1]。

现在,如果BR[j1] >=-i,我们发现,在[j1, TL[i]的幅度中,森林最大,并且继续这样做。

一旦我们找到了(TL[i]、BR[j])候选人,我们就能够忽视今后(i)阵列。

这使得我们在O(n)时间处理每一分校,给O(n^2)总算法。

我留下了许多细节,并做了一个概要,因为时间已经太长。 有理由对此作出澄清。

Phew.

Answer 2

I don t know why you can get an O(n^2) algorithm. Mathematically, it is impossible. Let s say you have an NxN matrix. You need to check: 1. 1 matrix of size: NxN, 2. 2*2 matrices of size: (N-1)x(N-1), 3. 3*3 matrices of size: (N-2)x(N-2), ....

In total, you have to check: 1+ 2^2 + 3^2 + ... + N^2 = N(N+1)(2N+1)/6. So any algorithm cannot do better than O(N^3)

Answer 3

<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]<<"	";
        }
        cout<<endl;
    }
    cout<<answer<<endl;
    return 0;
}

Answer 4

/* 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); 
}

友情链接