use*_*288 6 c c++ algorithm performance data-structures
给定方阵,每个单元格为黑色或白色.设计算法以找到最大子方块,使得所有4个边界都是黑色的.
我有O(n ^ 2)算法:
从左到右扫描每列,对于每列中的每个单元格,扫描每一行以找到具有后边框的最大子广场.
有更好的解决方案吗？
谢谢
O(n ^ 2)是可能的.我想它是最佳的,因为你有n ^ 2个细胞.
请注意,任何正方形的左上角和右下角都位于同一对角线上.
现在,如果我们可以在O(n)时间内处理每个对角线,我们将有一个O(n ^ 2)时间算法.
假设我们有一个左上角的候选人.我们可以计算它下面的连续黑色单元格的数量,并在它的右边,并取两个中的最小值并称之为T.
对于右下角的候选者,我们可以计算它左边的连续黑色单元格的数量,并且在顶部并且取两个中的最小值,称之为B.
一旦我们得到两个数字T和B,我们可以判断给定的左上角,右下角的候选者是否实际上给了我们一个带有所有黑色边框的正方形.
现在,通过在整个矩阵中进行四遍(How？),可以在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和,i和j形成一个正方形B[j] >= j-i+1.
即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)时间内完成).
现在给定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)个总算法.
我遗漏了很多细节并给出了草图,因为它已经太长了.随意编辑,并附上说明.
唷.
| 归档时间： |
|
| 查看次数： |
2258 次 |
| 最近记录： |