algorithm - 给定一个网格，分割为n block 不同形状和大小的算法

Question

有一个 iOS 游戏，Unblock Me ，它采用给定的网格/板并将该网格分割为不同大小和形状的 block 。

有人可以告诉我完成此类任务的算法是什么样的吗？给定一个网格，将网格分割为更小的部分，就像 Unblock Me 中的 block 一样，但也包括正方形和矩形。我仍然想自己弄清楚，但我在开始时遇到了一些麻烦。

编辑:

此外，理想情况下，解决方案不会在原始网格内留下任何空白空间，它会以这样一种方式进行分割，即在给定特定分割数的情况下使用所有点。

Answer 1

您可以有一些标准的 block 大小和定义的网格大小。例如，以 Unblock Me 为例:grid_size 可以是 4*4，block_size1 可以是 3*1，block_size2 可以是 2*1 等等。然后，您可以定义，或者作为输入，您想要在网格中的 block 数。使用动态规划或递归回溯来填充具有这么多 block 的网格。