高效搜索二维数组中的有效位置

Question

快速说明：请随意以任何选择的语言回答

我想快速有效地搜索二维数组以找到放置对象的第一个有效位置。对于被认为有效的位置，这意味着指定高度和宽度的对象将适合仅标记为 0 的区域。对于这种情况，您可以想象我们指定的对象的高度和宽度 > 1，并且二维数组中将存在一个有效位置。例如，假设我有以下 2D 数组

[
 [0,0,0,0,0,0,1],
 [0,1,0,0,0,1,0],
 [0,0,0,1,0,0,0],
 [0,1,0,0,0,0,0],
 [0,0,0,0,0,0,0],
 [0,0,0,0,0,0,0],
 [0,0,0,0,0,0,0]
]

并且一个高度为 3 、宽度为 3 的对象，该函数应该返回一个以下面的行和列作为第一个有效位置的对象

{row: 2, col:4}

。第一个有效位置是指左上角，其中未知高度和宽度的对象可以适合 2D 数组并覆盖每个元素均为 0 的区域。

也许我们能做的最好的就是 n*m 并且必须搜索每个元素。我只是一厢情愿地认为有些领域我可以跳过，因为我知道它们行不通。使用上面的示例，我尝试从对象的宽度开始搜索。在这种情况下，我将从 (0,2) 开始搜索。我会先搜索到 (2,2)，然后再向左搜索。一旦我在 (1,1) 处发现碰撞，我就知道我不必搜索 (0,0) 或 (1,0)。我要解决的是以下两点：

1. 如何提高效率而不是重新检查我已经检查过的区域。
2. 如何提高效率并且不检查不可能适合我的物体的区域。

我的思维过程是某种 bfs/dfs 算法，但我在检查我知道无效的区域时遇到了问题。我需要一种方法来有效地知道什么是无效的，以避免在这些领域花费时间

Answer 1

我会采用以下方法：为每一行设置一个“零”（有效）位置及其长度的数组。我们称之为 [pos,len]

0 [0,6]
1 [0,1],[2,3],[6,1]
2 [0,3],[4,3]
3 [0,1],[2,5]
4 [0,7]
5 [0,7]
6 [0,7]

当你寻找 3,3 的矩形时，你只剩下

1 [2,3]
2 [0,3],[4,3]
3 [2,5]
4 [0,7]
5 [0,7]
6 [0,7]

由于您想要的高度为 (3,3)，行应该在长度位置上有正确的重叠。从第 1 行 [2,3] 开始。 row2 [0,3] 中是否有重叠，其中：

pos2 + len2 - pos1 >=3 and pos1 + len1 - pos2 => 3

this would give us 0 + 3 - 2 >= 3 and 2 + 3 - 0 => 3 FALSE

现在我们可以取 row2 [4,3] 中的下一个，这给了我们另一个 FALSE

与 row3 [2,5] 相比，是时候忘记 row1 并移动到 row2[0,3]

等等等等

当你有 2 次 TRUE 时，你就找到了你的位置。 2 因为它是矩形高度 (3) -1

Answer 2

假设我们有一个大数组，其中填充了

1s

和

0s

，它们仅由于该数组中可用矩形中的对象位置而发生变化。

第一步是计算所有对象的所有可用矩形。

我们为每个对象大小使用容器。
例如，大小为 (3x4) 的对象的容器将在数组中存储每个对象左上角的 (x,y) 坐标。使用另一个容器来存放 (2x4) 物体；另一个为 (5x1)；等等。

请注意，位置可能会重叠。也许 (4,5) 对象的 (2,3) 位置与同一 (4,5) 对象的 (3,3) 位置或与 (1,2) 对象重叠。不关心。

容器可以按某些标准排序：最小 x、最小 y、最小 x+y 等。

重点是，当我们搜索给定对象（NxM）时，我们只需在其（NxM）应有的容器中搜索，如果已排序，则获得第一个。

一旦我们确定了位置，就必须更新受影响的容器。
我们必须实现一个盒子与盒子的交集（这很简单，仅适用于角点）来判断是否必须删除容器中的某个位置，并判断是否出现新的较小位置。

诀窍在于，使用已排序的容器比逐个单元检查要快得多。但对于小型阵列或只是一堆位置而言，情况并非如此。