arrays - 如何有效地找到特定尺寸的空心矩形？

Question

背景

我有一个分成正方形的矩形区域(这是我正在制作的游戏)。我在我的代码中将其表示为一个简单的二维 boolean 数组:

  ┌──┬──┬──┬──┬──┐
  │  │  │  │  │  │ X = X-value, also increasing width
  ├──┼──┼──┼──┼──┤ Y = Y-value, also increasing length
  │  │  │  │  │  │
  ├──┼──┼──┼──┼──┤
  │  │  │  │  │  │
  ├──┼──┼──┼──┼──┤
  │  │  │  │  │  │
  ├──┼──┼──┼──┼──┤
^ │  │  │  │  │  │
Y └──┴──┴──┴──┴──┘
   X >

一些正方形可以被建筑物等占用成矩形，就像这个输入(** = taken):

┌──┬──┬──┬──┬──┐
│**│**│  │  │  │ 3 taken rectangles
├──┼──┼──┼──┼──┤
│**│**│**│**│  │
├──┼──┼──┼──┼──┤
│  │  │**│**│  │
├──┼──┼──┼──┼──┤
│  │  │**│**│  │
├──┼──┼──┼──┼──┤
│**│  │**│**│  │
└──┴──┴──┴──┴──┘

在 2D boolean 数组中，“taken”方 block 设置为 true，“open, non-taken”方 block 设置为 false.

我的问题

我需要找到特定大小的所有“开放”矩形(未采用)。这是因为我需要找到所有 可能的空间来放置下一个建筑物。例如，根据上图，如果我想获得所有“开放”的 1x2 矩形，我应该获得这些输出:

┌──┬──┬──┬──┬──┐
│**│**│1 │12│2 │ 3 taken rectangles (input)
├──┼──┼──┼──┼──┤ 4 open 1x2 rectangles (output)
│**│**│**│**│  │ Open rectangles are numbered
├──┼──┼──┼──┼──┤ 
│3 │3 │**│**│  │ Rectangles can overlap.
├──┼──┼──┼──┼──┤ The '12' square represents the overlapping
│4 │4 │**│**│  │ of rectangle 1 and 2.
├──┼──┼──┼──┼──┤ 
│**│  │**│**│  │ (Haha, my diagram kind of looks like old Minesweeper)
└──┴──┴──┴──┴──┘

我做了什么

这是我测试过的(暴力搜索，代码是 C# 和一些伪代码):

List<Rectangle> findOpenSpaces(boolean[][] area, int width, int length) {
    List<Rectangle> openSpaces = new List<Rectangle>();
    boolean open = true;
    // Loop through all rectangles with size "width" and "length"
    for x = 0 to (total area length) - length {
        for y = 0 to (total area width) - width {
            // Check this rectangle to see if any squares are taken
            Rectangle r = new Rectangle(x, y, width, length);
            if checkRectangle(area, r) returns true {
                // rectangle was fully open, add to the list
                openSpaces.Add(r);
            }
        }
    }
    return openSpaces;
}

boolean checkRectangleIsOpen(boolean[][] area, Rectangle r) {
    for i = r.x to r.width {
        for j = r.y to r.length {
            if area[i][j] is true {
                // means that this square in the rectangle is taken,
                // thus the rectangle is not fully open
                // so return false (not open)
                return false;
            }
        }
    }
    return true; // no square in the rectangle was taken
}

struct Rectangle { // just a struct to help store values
    int x, y, width, length;
}

问题

上面的(伪)代码有效，但是如果你看一下它，是时候 O(n^4) :( 我认为，因为四个嵌套的 循环，但我不是专家。另外，在游戏中，矩形区域的总大小为 50x50，而不是像我这里的示例那样的 5x5。每当我这样做时，游戏明显滞后操作。

我用 Google 搜索了这个，但我不确定如何称呼这个问题。如果有人能告诉我一个有效的算法来完成这项任务，我将不胜感激。谢谢:)

Answer 1

一些快速的思考会表明，您根本无法比 O(NM) 更快地执行此操作，因为至少有那么多可能的输出。您已经有了一个 O(N^2M^2) 的解决方案，所以让我们看看能否找到一个 O(NM)。

我要做的是，不是寻找可以形成大小为 a x b 的矩形的位置，而是寻找不能的位置。

也就是说，像这样(伪代码):

for each taken square:
    for each rectangle starting position:
        if rectangle at starting position includes this taken square,
            mark starting position as non-tenable

如果您的矩形很小(如上面的 1x2 示例)，这(高效实现)就足够了。但是，对于一种不依赖于渐近速度的矩形大小的方法。 . .

考虑 (x,y) 被占用。那么与这个点重叠的矩形本身就形成了一个矩形，那个范围内的东西都不能用。所以我们想将一个(离散的)range 标记为不可用。这可以通过二维 Fenwick tree 来完成。 ，每次更新或查询的成本为 O(log N log M)。要将范围 (x1, y1, x2, y2) 标记为“正在使用”，我们:

1. 将 (x1, y1) 加一
2. 将(x1, y2)减一
3. 将 (x2, y1) 减一
4. 将(x2, y2)加1

因此我们最终对每个使用的正方形执行 4 次 2D Fenwick 树操作，其中最多 O(NM)。然后，当我们完成后，我们检查每个可能的起始位置的值:如果它为零，则它是一个有效的起始位置。如果它非零，则不能使用。

总成本:O(NM log N log M)。虽然您可能会更快地执行此操作，但这种方法的实现速度/大小比非常好(二维 Fenwick 树大约需要十行代码来实现)。