arrays - 用未知形状填充网格

Question

作为输入，我给出了 0 的 2D 网格，其中很少有 -1 位置指示无法填充的位置和某些形状的蓝图(如俄罗斯方 block 游戏)

 ex. of grid              ex. of shapes

 0  0  0  0  0  0  0        1 1 1     2 2 2     3 3
-1  0  0  0  0  0  0        1           2
-1  0  0  0  0  0  0        1
 0  0  0  0  0 -1  0
 0  0  0 -1  0  0  0

算法应该输出填充给定形状的网格总是必须使用所有形状一次我可以旋转形状，我应该总是得到可以填充的网格和形状。 我研究了像洪水填充算法这样的算法，但我并没有真正看到在这里使用它的方法。是否有可能以不同于暴力破解的方式来做到这一点？

Answer 1

这是我对如何解决这个问题的想法:

对于每个形状，似乎有 4 种可能的类型(包括原始形状)例如:

1 1 1          1    1 1 1    1
1       ->     1        1    1
1          1 1 1,       1,   1 1 1 

现在假设有 s 个形状，那么总共有 4s 个形状。

从 4s 形状中组合出一个图形，如下所示:

  2
1 2 2
1 2 3 3
1 1 1 

或

1 1 1
1 2 3 3
1 2 2
  2 

或

1 1 1 3 3
1 2 2 2
1   2

或

(4s)^2 = 16s^2 可能性中的任何此类数字。

实际上不止是16s^2，因为它不仅仅是形状的串联，你需要贪婪地寻找空位，并试图把它塞进去。 :(

现在您手中有了一个图形，请在您的网格中寻找相同的形状。

例如寻找

1 1 1
1 2 3 3
1 2 2
  2 

我会寻找

0 0 0
0 0 0 0
0 0 0
  0 

在原始网格中。

那么这似乎是一个在原始矩阵中找到那个数字的问题。

另见 this这是一个类似但不完全相同的问题，关于寻找形状。