python - 如何用 2 * 3 block 占据 10 x 10 block ，并且不让其他人推另一个 2 * 3 block

Question

我想找出可以填充 100 个像素的 2 * 3 block 的最小数量，并且不允许填充任何其他 2 * 3 block ，如下图所示。

2 * 3 in 10 * 10 = 6

或者另一个例子:

2 * 1 in 5 * 7 = 14

我进行了很多搜索，但到目前为止还没有成功。我不需要任何代码，但我想要算法名称或任何建议来找到我的方法。

任何帮助将不胜感激。

Answer 1

从评论中我了解到，我们无法旋转矩形。那么我们就采用下面的方法:

想象一下，您想要解决同样的问题，但仅限于直线，其中矩形大小为 1xGridW 网格中的 1xRectW。

我将使用“X”表示矩形单元格，“0”表示空单元格。 示例有 1x3 矩形和 1x10 网格。

从左侧，我可以保留最大的空(RectW - 1)单元格:

00XXX00000

然后我可以在前一个矩形的右侧最多留出空的(RectW - 1)单元格:

00XXX00XXX

现在我们添加另一个维度。假设我们有 2 行。我可以在这里继续使用相同的逻辑，但我将复制整个第一行，而不是复制矩形:

00XXX00XXX
00XXX00XXX

现在我们想对 10x11 网格中的 2x4 矩形执行相同的操作。这里我们得到了高度为 2 的矩形，因此第一步将使用 2 行:

000XXXXXXXX
000XXXXXXXX

并将其扩展为行:

00000000000
000XXXXXXXX
000XXXXXXXX
00000000000
000XXXXXXXX
000XXXXXXXX
00000000000
000XXXXXXXX
000XXXXXXXX
00000000000

正如您所注意到的，我们在顶部添加了额外的 (RectH - 1)。

如果你注意的话，你会发现，实际上我们只是在进行除法和四舍五入。

所以在Python中我们可以用这样的数学抽象来表达这个想法:

def solver(rectH, rectW, gridH, gridW) -> int:
    w = round(gridW / (rectW * 2 - 1))
    h = round(gridH / (rectH * 2 - 1))
    return w * h

结果:

>>> solver(2, 3, 10, 10)
6
>>> solver(2, 1, 5, 7)
14