algorithm - 在 1 和 0 的二维数组中找到一个 1 的矩形

Question

我有一个二维对象数组，如果对象的 clicked 属性设置为 true，则应将其视为“1”，否则应视为“0”。这些是被选中的块。我需要检查选定的框是否形成一个矩形。解决此问题的最佳方法是什么？

Answer 1

高水平：

• 跟踪最外面的 1。
• 数所有的 1。
• 如果计数等于最外面的 1 包围的面积，我们就有一个矩形。

伪代码：

left = width + 1
right = 0
top = height + 1
bottom = 0
count = 0

for x = 1 to width
for y = 1 to height
  if grid[x][y] == 1
    left   = min(left  , x)
    right  = max(right , x)
    top    = min(top   , y)
    bottom = max(bottom, y)
    count++

if count > 0 and count == (right-left+1)*(bottom-top+1)
  print "We have a rectangle!"
else
  print "We don't have a rectangle!"

Answer 2

你可以这样解决它：

• 搜索第一个元素 1
• 水平向右走，然后向下，然后向左，然后向上
• 如果你回到原点，你有一个矩形
• 然后确保所有其他元素为0。

这个算法是 O(n^2) 并且如果你只允许一个矩形就可以工作。如果你有多个矩形，它会变得复杂..

Answer 3

我会做这样的事情（伪代码）：

// your 2d-array / matrix (N is the number of lines, M the number of columns)
m[N][M] = ...

// x coord of top left object containing 1
baseM = -1
baseFound = false
// expected width of rectangle
width = 0
widthLocked = false

// this is set to true after we started recognizing a rectangle and encounter
// a row where the object expected to be 1 in order to extend the rectangle
// is 0.
heightExceeded = false

// loop over matrix
for i = 1 to N: // lines
    // at the beginning of a line, if we already found a base, lock the width
    // (it cannot be larger than the number of 1s in the row of the base)
    if baseFound: widthLocked = true

    for j = 1 to M: // columns
        if m[i][j] == 1:
            if not baseFound:
                baseM = j, baseFound = true
                width = 1
            else:
                if j < baseM:
                    // not in rectangle in negative x direction
                    return false
                if heightExceeded:
                    // not in rectangle in y direction
                    return false
                if widthLocked:
                    // not in rectangle in positive x direction
                    if j - baseM >= width: return false
                 else:
                    width = j - baseM
        elseif baseFound:
            if widthLocked:
                // check if we left the rectangle and memorize it
                if j == baseM: heightExceeded = true
                if not heightExceeded:
                    // check if object in rectangle is 0
                    if j > baseM && j < baseM + width: return false
if baseFound:
    return true
else:
    // what is the expected result if no rectangle has been found?
    return ?

在 O(n) 中运行。当心错误。

注意：大多数编程语言都有从 0 开始的数组，因此您可能需要i从0to循环N - 1，与 for 相同j。