背景
我有一个矩形区域分成许多小正方形（这是我正在制作的游戏）。我在代码中将其表示为简单的二维boolean数组：
┌──┬──┬──┬──┬──┐
│ │ │ │ │ │ X = X-value, also increasing width
├──┼──┼──┼──┼──┤ Y = Y-value, also increasing length
│ │ │ │ │ │
├──┼──┼──┼──┼──┤
│ │ │ │ │ │
├──┼──┼──┼──┼──┤
│ │ │ │ │ │
├──┼──┼──┼──┼──┤
^ │ │ │ │ │ │
Y └──┴──┴──┴──┴──┘
X >
有些方块会被建筑物等长方形占据，例如这个输入 (**代表已占据的方块)：
┌──┬──┬──┬──┬──┐
│**│**│ │ │ │ 3 taken rectangles
├──┼──┼──┼──┼──┤
│**│**│**│**│ │
├──┼──┼──┼──┼──┤
│ │ │**│**│ │
├──┼──┼──┼──┼──┤
│ │ │**│**│ │
├──┼──┼──┼──┼──┤
│**│ │**│**│ │
└──┴──┴──┴──┴──┘
我的问题
我需要找到所有指定大小的“open”矩形（未取走）。这是因为我需要找到放置下一个建筑物的所有可能空间。例如，在前面的图中，如果我想获取所有“open”的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) :( （我想是因为有四个嵌套的for循环，但我不是专家）。另外，在游戏中，矩形区域的总大小为50x50，而不是像我这里举的例子那样是5x5。每当我执行此操作时，游戏都会明显地出现卡顿。
我在谷歌上搜过这个问题，但我不确定应该如何称呼它。如果有人能为我展示一个有效的算法来完成这个任务，我将非常感激。谢谢 :)