c++ - 大きな2D行列が与えられた場合、小さいサイズnの2D行列をいくつ一意に適合させることができますか？

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)

すべての位置を再帰的に試して、canPlace3x3オブジェクトを配置します。

これを行うときは、配置する領域に障害物のマークを付け、障害物があるかどうかを確認してから配置します。

上記の複雑さ=？（より多くの可能な配置により、解決策を非常に迅速に見つけることができます）

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

上記の複雑さ=O(n^2)

全体の複雑さ=O(n^2 log n + ?)