3

问题是，给定一个所有单元格为黑色或白色的矩阵，找到所有边界单元格为黑色的最大尺寸子矩阵（内部单元格不必是黑色的）。

目前我最多能想到一个O(N^4)解决方案。为此，我制作了 2 个辅助表，一个是每个单元格的每一行右侧连续黑色单元格的计数，另一个是每个单元格该列中连续黑色单元格的计数。然后我这样做：

for each row (i):
   for each cell (i,j):
     for each window (1..n-j):
       if auxrow[i,j+window]-auxrow[i,j] == window:   #so, all cells in this window is black
         colsleft = auxcol[i,j]
         colsright = auxcol[i,j+window]
         botttom_row = min(colsleft,colsright)
         for bot in (row..row+mincol):
            if auxrow[bot][j+window]-auxrow[bot][j] == window:
              maxlen = ... #do whatever to save this sub-matrix as answer

如何改进这个解决方案？我在Topcoder看到了一些有趣的讨论，特别是 Rem( O(N^2*log N)) 的回答，以及 Tomek 提出的后续改进，但我都无法理解这两种解决方案！有人可以提供比我更好的解决方案，或者解释这些算法吗？

4

1 回答 1

3

O(N^3) 是可能的。

对于每个单元格计算顶部和右侧的连续黑色单元格（可以在 O(N^2) 时间内完成）。

对于每一列（比如第 i 列），你会得到一个包含 n 个元素的数组，它维护着正确的信息，比如 R_i。

现在给定数组 R_i，我们计算 n 个其他数组（所以 Omega(N^3) 空间）如下：

对于每个 d 使得 1 <= d <= n，您创建一个包含 n 个元素的新数组 D_id，如果 R_i 中的相应值即 R_i[j] < d，则它在元素 j 处具有 n+1。如果 R_i[j] >= d，则 D_id 中的相应条目将等于 j。

基本上给定 ad 和 i，使用数组 D_id，我们可以判断第 i 列中的哪些单元格可能是宽度为 d 的矩形的端点。

现在为范围最小查询预处理每个 D_id：即给定一个范围 [u,v]，我们可以在 O(1) 时间内找到子数组 D_id[u...v] 中的最小值。

由于您为每一列花费 O(N^2) 时间，因此这一步是 O(N^3) 时间。

现在要找到一个矩形，您需要考虑每一行并选择可以作为矩形一个边缘的每一对点。将这些点视为矩形的左下角和右下角端点。

假设考虑的点在 i 和 j 列上，矩形的宽度是 d。

现在找到矩形的最大可能高度（使用我们之前计算的最高值）。说是h。

现在，如果您正在考虑的行是 r，那么您现在对范围 (r, rh] 上的 D_id 运行范围最小值查询。如果最小值 <= n，那么您找到了一个矩形。

由于您将考虑 N^3 个这样的可能对（每行 N^2 个点），因此总运行时间为 O(N^3)。

于 2012-11-03T06:36:11.277 回答