给定一个方形矩阵，每个单元格都是黑色或白色。设计一种算法，以查找最大子正方形，使得所有4个边界都是黑色。
我有一个O(n^2)的算法：
从左到右扫描每列，在每列中的每个单元格中，扫描每行以查找具有黑色边框的最大子正方形。
是否有更好的解决方案？
谢谢
在一个由黑色和白色组成的方阵中，设计一个算法以找到最大子正方形，使得该正方形的四个边界都是黑色。
7
- user1002288
5
疯狂的想法：如果您的矩阵非常大，也许使用选择良好的动量空间基础的离散傅里叶变换可以很好地估计所得到的方阵的大小。不过我不知道这是否切实可行。 - Kerrek SB
2对于每个单元格进行线性数量的工作听起来对我来说像是O(n^3)。 - simonpie
1你能展示一下你的O(n^2)算法吗？ :) 我在这里看到了一个讨论 http://discuss.techinterview.org/default.asp?interview.11.445656.19，大家都卡在了O(n^3)。 - John Humphreys
如果您以这种方式扫描，那么您就不必再次扫描先前遇到的单元格，对吗？ - harold
一个子正方形的“边界”是指它的外部行和列，还是周围的行和列？例如，对于子正方形（5,5）-（10,10），它是从（5,5）到（5,10）到（10,10）到（10,5）到（5,5），还是从（4,4）到（4,11）到（11,11）到（11,4）到（4,4）？ - James Waldby - jwpat7
4个回答
5
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' > 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，我们需要回答以下查询：
什么是最大的j，使得TL[i] >= j且BR[j] >= -i？
现在假设我们能够处理BR的范围最大查询（可以在O(m)时间内完成）。
现在，在范围[i，TL[i]]中给定TL[i]，我们找到BR的最大值，称之为BR[j1]。
如果BR[j1] >= -i，我们在范围 [j1, TL[i]] 内找到 BR 的最大值并继续这样做。
一旦我们找到(TL[i],BR[j])的候选者，我们可以忽略数组BR[1...j]以便未来的i。
这使我们能够以O(n)时间处理每个对角线，从而得到一个O(n^2)总算法。
我已经省略了很多细节并给出了一个草图，因为它已经太长了。请随意编辑并进行澄清。
呼。
- user127.0.0.1
1
我不知道为什么你能得到一个O(n^2)的算法。从数学上讲，这是不可能的。
假设你有一个NxN矩阵。你需要检查：
1. 大小为NxN的1个矩阵，
2. 大小为(N-1)x(N-1)的2x2矩阵，
3. 大小为(N-2)x(N-2)的3x3矩阵，
....
- Hill Nguyen
0
/* 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);
}
- opmiss
-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;
}
- vishnu sankar
2
3我认为你的代码解决了一个不同的问题。你的代码难道不是找到所有黑色正方形中最大的子正方形吗？而这个问题要求找到最大的子正方形，其中每个边界正方形都是黑色。 - John Kurlak
1它也没有解释算法问题的算法，只是简单地倾倒了一些代码。 - undefined
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接