如何找到0和1的二维矩阵中的矩形数量？

问题描述：

我已经在SO上搜索了许多帖子以及其他在线资源。他们中的大多数提供了一个解决方案，用于在2D矩阵中查找矩形的最大面积，我知道。但是，我很想知道如何找到2D矩阵中矩形数为（表示为1s）的矩形数。如何找到0和1的二维矩阵中的矩形数量？

更新： 道歉不澄清的情况下，以一个长方形什么分类 - 它被认为是一个矩形，如果一定周边内的细胞是充满以1s。

对于rectabgle来算，做的正好角落需为1，或双方，还是矩形必须充满1s？ –

@ OleV.V。，我更新了我的问题。 –

答

这里是一个非优化的版本，应该给予正确的结果：

int sum = 0; 
for (int row = 0; row < n; row++) { 
    for (int col = 0; col < m; col++) { 
     // count all rectangles with top left corner at (row,col) 
     int upperLimit = m; // this number sets the max width that rectangles with greater 
          // height can have (depends on the 1s in the rows above) 
     for (int r = row; r < n && matrix[r][col] == 1; r++) { 
      int c = col; 
      for (; c < upperLimit && matrix[r][c] == 1; c++) 
       sum++; 
      upperLimit = c; 
     } 
    } 
}

我承认在考虑是否为提问者编写代码时总会找到平衡点。通常我们说我们不这样做，主要是因为我们不想吸引“给予编码”这类问题。我认为这是我们可以安全避免的情况之一，并且可以仅给出解释性答案。我比这个更喜欢伪代码。 –

在我看来，没有10是正确的答案，我不知道你是如何得到8的。如果我们从左到右，从上到下，它是4 + 1 + 2 + 2 + 1 = 10。的伪代码非常模糊，并且比它的复杂得多。 @ OleV.V。 – maraca

感谢您解释我的计数错误。我犯了一个错误的一个原因是你的代码有点棘手，应该得到比你给出的更好的解释。 –

答

一些伪代码：

for x_0 in rows: 
    for x_1 > x_0 in rows:  # symmetry-reduction: x_0 always "top" 
     for y_0 in columns: 
      for y_1 > y_0 in columns: # symmetry reduction: y_0 always "left" 
       if mat[x_0, y_0] == mat[x_0, y_1] == mat[x_1, y_0] == mat[x_1, y_1] == 1: 
        found rectangle!

请记住：这是伪代码（部分基于Python风格）和布尔评价不一样，在大多数语言工作！

对称减少不仅可以提高性能，而且在计数时也很重要。在视觉上有相同的矩形，其中x_0和x_1只是承担不同的角色（左和右点）。你必须决定如何计算这一点。

编辑：在Ole V.V.的评论上面，我意识到确实存在非常不同的解释。这些大部分可以用上面的伪代码来实现，但是在内部级别上有不同的检查。但那可能是你的工作（并且在某些情况下可能有更多的调整方法）！

在这里，我假设，一个矩形只是由1在4个角落定义！

编辑：新矩形的定义之后，内部检查的变化：

if all(mat[x_0:x_1, y_0:y_1]) # python/numpy inspired pseudo-code!

所以基本上你可以检查由4边界点所定义的所有值。这很简单，可以解决您的问题。

但是，当然你可以更有效率。添加一些二进制标志可能是明智的，它指示当前矩形（它们正在增长）是否仍然只填满1。其实你可能需要2个二进制标志，每个维度1个。如果情况并非如此，那么你可以尽早停止。

@sashcha，谢谢你的回答。请检查我更新的问题。我已经澄清了什么归类为矩形的细节。 –

如何找到0和1的二维矩阵中的矩形数量？

相关推荐