c++ - 在方阵中，每个单元格都是黑色或白色。设计一种算法来找到最大白色子方格

Question

关闭。这个问题需要多问 focused 。目前不接受答案。

---

想要改进此问题吗？更新问题，使其仅关注一个问题 editing this post .

已关闭 8 年前。

Improve this question

在方阵中，每个单元格都是黑色或白色。设计一个算法来找到最大白色(整个子方格都是白色)子方格。

O(n^2) 的解决方案:从左到右扫描每一列，对于每一列中的每个单元格，扫描每一行以找到最大的白色子方 block 。

你有更好的解决方案吗？

谢谢

Answer 1

首先请注意，您的解决方案不是 O(n^2)，它更像是 O(n^4)，因为对于每个单元格，您都会寻找最大矩阵的大小可达 O(n^2) 本身，因此总计为 O(n^4)。

但是可以在O(n^2)中完成:

首先，定义2个辅助函数(以矩阵形式实现):

whitesLeft(x,y) = number of adjacent white cells on the same row to the left from x,y - exclusive of x,y
whitesUp(x,y) = number of adjacent white cells on the same column up from x,y -  exclusive of x,y

现在，定义递归函数:

D(0,y) = 0     if (0,y) is black
         1     otherwise
D(x,0) = 0     if (x,0) is black
         1     otherwise
D(x,y) = 0                                                         if  x,y is black
         min{ D(x-1,y-1), whitesLeft(x,y), whitesUp(x,y) } + 1     otherwise

这个想法是用D(x,y)计算以(x,y)结束(右下)的最大正方形。通过查找左侧的最小单元格、向上的单元格以及以 (x-1,y-1) 结尾且仅包含白色单元格的子矩阵来计算此正方形。

请注意，可以使用 D ynamic Programming 有效计算 D(x,y) O(n^2)，计算辅助函数(矩阵)的预处理也是O(n^2)。

完成后，发布过程 D 来查找任何 (x,y) 的 D(x,y) 的最大值> 得到结果 - 这也是O(n^2)。