能够适合一个空间的最大图案数量

Question

能够适合一个空间的最大图案数量

3

假设您有一个随机初始化的布尔数组 A，大小为 n-by-m，并且假设您有一个随机初始化的布尔数组 B，大小为 p-by-q，其中 p <= n 且 q <= m。

我想知道最多可以将多少个 B 放入 A 中：如果对于每个 0 <= i < p 和每个 0 <= j < q，使得 not (A[k + i, l + j] and B[i, j]) 都是 true，则我认为 B 可以放入 A 中，其中 0 <= k < n - p 且 0 <= l < m - q。

简单来说，我有一个模式和一个地图带有障碍物，并且我想知道最多可以将多少个模式放入该地图中。我使用约定，即 true 和 false 分别表示占用和未占用空间。

我目前正在通过递归解决此问题，但效率非常低下。我想知道是否有更好的方法。即使是一个参考资料，我也将不胜感激。

编辑1：我对最大非重叠 B 的数量感兴趣。

编辑2：让 A 是以下数组：

让 B 是以下数组：

请注意，我让 B 及其中心的颜色不同仅出于可视化目的。

然后我可以以以下两种方式将 B 放入 A 中：

在第一幅图像中，我能够放置六个 B。然而，在第二幅图像中，我能够放置九个。我对最大数量感兴趣。

- wjmolina

如果您使用一个矩阵和另一个矩阵的对角镜像进行2D卷积，则与模式中的1的数量相等的条目给出匹配位置。不确定最大是否意味着不重叠。 - David Eisenstat

1

你能添加一个例子吗？你当前的解决方案的复杂度是多少？这些矩阵可以有多大？ - juvian

@juvian，我添加了一个例子。 - wjmolina

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- TimD1 · Accepted Answer

我能想到的最直接的方法是最坏情况下O(mnpq)。将矩阵B视为一个模板，它位于矩阵A的顶部。对于A中的每个位置x，y，在该位置（x，y）上可以放置B并且B的左上角在该位置上（有(m-p)(n-q)个这样的位置），检查对于0 <= i < p和0 <= j < q，B [i] [j]和A [x + i] [y + j]是否都不是1。计算出发生这种情况的位置数。此代码将使用四个嵌套的if循环，并完全避免递归。

如果A是稀疏的（很少有位置是true），则以向后工作为更有效，注意B无法放置的位置。从大小为A的矩阵C开始初始化为true。扫描所有A[x][y]为真的位置，并注意值，如果将B的左上角放置，则B中的true会与A中的true发生碰撞。将出现这种情况的所有C的值设置为false。完成后，求和矩阵C将为您提供没有发生碰撞的位置数。