假设您有一个 bool 值 n -by- m , 随机初始化数组 A ，并假设您有一个 bool 值 p -by- q , 随机初始化数组 B , 其中p <= n和 q <= m .
我想知道 B 的最大数量适合 A : 我说 B适合 A如果not (A[k + i, l + j] and B[i, j])是true对于每个 0 <= i < p每个0 <= j < q , 其中0 <= k < n - p和 0 <= l < m - q .
简单来说，我有一个图案和一张带有障碍物的 map ，我想知道适合该 map 的图案的最大数量。我使用 true 的约定和 false分别代表占用空间和未占用空间。
我目前正在通过递归解决这个问题，但它非常低效。我想知道是否有更好的方法。即使是引用，我也会很感激。
编辑 1:我对非重叠的最大数量感兴趣 B
编辑 2:让 A是以下数组:
让B是以下数组:
注意我让B仅出于可视化目的，它的中心具有不同的颜色。
然后我可以装B进入A有以下两种方式:
在第一张图片中，我可以放置六个 B秒。然而，在第二张图片中，我能够容纳九个。我对最大数量感兴趣。
最佳答案
我能想到的最直接的方法是最坏的情况 O(mnpq)。想矩阵B作为位于矩阵顶部的模板 A .对于每个位置 x,y在 A其中 B可以将它的左上角放在该位置 ( x,y ) 以便所有矩阵 B包含在 A 中(有 (m-p)(n-q) 个位置)，检查每个 0<=i<p和 0<=j<q , B[i][j]和 A[x+i][y+j]两者都不1 .计算发生这种情况的位置数。此代码将使用四个嵌套的 if循环，并完全避免递归。
如果A恰好是稀疏的(很少有位置是 true )，向后工作会更有效率，注意 B 的位置不能放置。以矩阵 C 开始尺寸A初始化为 true .扫一扫A对于 A[x][y] 的所有职位为真，并记下 B 左上角的值被放置，一个true在 B会与 true 相撞在 A .设置 C 的所有值发生这种情况等于 false .完成后，求和矩阵 C将为您提供未发生碰撞的位置数。
关于algorithm - 适合空间的最大图案数，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/50031996/