c++ - 给定一个大的二维矩阵，我可以唯一拟合多少个尺寸较小的二维矩阵？

Question

我有一个代表 3D 游戏的 2D 地形的大型 2D 矩阵 - 各种类型的墙壁和地板（泥土、岩石等）。例如，假设有一个 4x9 的岩石地板区域。我需要在 4x9 空间的每个 3x3 区域的中心放置一个对象，并在解析并排除 3x3 区域后，在每个 1x1 区域放置一个对象。

结果应该是放置 3x3 模板的 3 个对象和放置 1x1 模板的 9 个对象。

实现此算法的最有效方法是什么？

Answer 1

设canPlace为坐标的 BST。

for (x = 0:w)
for (y = 0:h)
  shouldPlace = true
  for (x2 = -1:1)
  for (y2 = -1:1)
    if (grid[x+x2][y+y2].isObstruction())
      shouldPlace = false
  if (shouldPlace)
    canPlace.add((x,y))

上面的复杂度是O(n^2 log n)

递归尝试所有canPlace位置以放置 3x3 对象。

执行此操作时，将放置它的区域标记为受阻，并在放置前检查是否受阻。

复杂度以上 = ? （更多可能的展示位置让我们能够非常快速地找到解决方案）

for (x = 0:w)
for (y = 0:h)
  if (grid[x][y].isEmpty())
    place1x1(x, y)

复杂度以上 =O(n^2)

总复杂度 =O(n^2 log n + ?)