在方阵中，每个单元格都是黑色或白色。设计一种算法来找到最大子方格，使所有 4 个边框均为黑色

Question

给定一个方阵，其中每个单元格都是黑色或白色。设计一种算法来找到最大子方格，使所有 4 个边框均为黑色。

我有 O(n^2) 算法：

从左到右扫描每一列，对于每列中的每个单元格，扫描每一行以找到带有后边框的最大子方块。

有更好的解决方案吗？

谢谢

Answer 1

C++ 代码：

#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 2

我不知道为什么你可以得到 O(n^2) 算法。从数学上来说，这是不可能的。
假设您有一个 NxN 矩阵。您需要检查：
1. 1个矩阵大小：NxN，
2. 2*2矩阵，大小：(N-1)x(N-1)，
3. 3*3矩阵，大小：(N-2)x(N-2)，
....

总共，您必须检查：1+ 2^2 + 3^2 + ... + N^2 = N(N+1)(2N+1)/6。
所以任何算法都不能比 O(N^3) 做得更好

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

O(n^2) 是可能的。我想这是最佳的，因为你有 n^2 个单元格。

请注意，任何正方形的左上角和右下角都位于同一条对角线上。

现在，如果我们可以在 O(n) 时间内处理每个对角线，我们就会有一个 O(n^2) 时间算法。

假设我们有一个左上角的候选者。我们可以计算其下方和右侧的连续黑色单元的数量，并取两者中的最小值并将其称为 T。

对于右下候选，我们可以计算其左侧的连续黑色单元的数量。到顶部并取两者中的最小值，称之为 B。

一旦我们有了两个数字 T 和 B，我们就可以判断给定的左上角、右下角候选是否实际上给了我们一个全黑的正方形边界。

现在，通过对整个矩阵进行四次遍历，可以在 O(n^2) 时间内计算每个单元格的这两个数字（如何？）。

那么让我们假设已经完成了。

现在考虑对角线。我们的目标是在 O(n) 时间内沿着这条对角线找到左上、右下对。

假设我们在数组 T[1...m] 中计算了 T，其中 m 是对角线的长度。类似地，我们有一个数组 B[1...m]。 T[1] 对应对角线的左上角，T[m] 对应对角线的右下角。与 B 类似。

现在我们按如下方式处理对角线，对于每个左上候选 i，我们尝试找到一个右下候选 j，它将给出最大的平方。请注意，j >= i。另请注意，如果 (i,j) 是候选者，则 (i',j) 不是，其中 i' > 。我。

请注意，如果 T[i] >= j-i+1 且 B[j] >= j-i+1，则 i 和 j 形成一个正方形。

即T[i] +i - 1 >= j 和B[j] -j - 1 >= -i。

因此，我们形成新的数组，例如 TL[k] = T[k] + k -1 和 BR[k] = B[k] -k - 1。

因此，给定两个新数组 TL 和 BR 以及一个 i，我们需要回答以下查询：

满足 TL[i] >= j 且 BR[j] >= -i 的最大 j 是多少？

现在假设我们能够处理范围最大查询的 BR（可以在 O(m) 时间内完成）。

现在给定 TL[i]，在 [i, TL[i]] 范围内，我们找到 BR 的最大值，即 BR[j1]。

现在如果 BR[j1] >= -i，我们找到 [j1, TL[i]] 范围内 BR 的最大值并继续这样。

一旦我们找到 (TL[i],BR[j]) 候选者，我们就可以忽略未来 i 的数组 BR[1...j]。

这使我们能够在 O(n) 时间内处理每个对角线，从而给出 O(n^2) 总算法。

我省略了很多细节并给出了草图，因为它已经太长了。请随意编辑此内容并进行澄清。

唷。