根据我的理解,我们不能旋转矩形.因此,我们使用以下方法:
想象一下,您想要解决相同的问题,但只针对直线,其中rect大小在1xGridW网格中为1xRectW.
我将使用"X"表示矩形单元格,"0"表示空单元格.
从左侧,我可以最大限度地保留空(RectW-1)单元格:
00XXX00000
然后我可以在前一个矩形右侧的max处保留空(RectW-1)单元格:
00XXX00XXX
现在让我们添加另一个维度.假设我们有两行.我可以在这里继续使用相同的逻辑,但不是复制矩形,而是复制整个第一行:
00XXX00XXX
00XXX00XXX
现在我们要对10x11网格中的2x4矩形执行相同的操作.这里我们得到了高度为2的矩形,因此我们将在第一步中使用2行:
000XXXXXXXX
000XXXXXXXX
并将其扩展到行:
00000000000
000XXXXXXXX
000XXXXXXXX
00000000000
000XXXXXXXX
000XXXXXXXX
00000000000
000XXXXXXXX
000XXXXXXXX
00000000000
正如您所注意到的,我们在顶部添加了额外的(RectH-1).
如果你们注意的话,你们会看到,实际上我们只是在用四舍五入进行除法.
在python中,我们可以用这样的数学抽象来表达这个 idea :
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