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

2 * 3 in 10 * 10 = 6

enter image description here

或者另一个例子:

2 * 1 in 5 * 7 = 14

enter image description here

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

任何帮助都将不胜感激.

推荐答案

根据我的理解,我们不能旋转矩形.因此,我们使用以下方法:

想象一下,您想要解决相同的问题,但只针对直线,其中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

Python相关问答推荐

如何在两列上groupBy,并使用pyspark计算每个分组列的平均总价值

重置PD帧中的值

为用户输入的整数查找根/幂整数对的Python练习

获取git修订版中每个文件的最后修改时间的最有效方法是什么?

如何在信号的FFT中获得正确的频率幅值

分解polars DataFrame列而不重复其他列值

类型对象';敌人';没有属性';损害';

PYTHON中的selenium不会打开 chromium URL

遍历列表列表,然后创建数据帧

如何强制SqlalChemy指向与连接字符串的默认架构不同的架构

设计添加和搜索词的数据 struct :Leetcode211

有理由将基于Django职业的观点个人化吗?

达到最大的Python Webhost资源

如何拟合返回2个输出的深度学习模型

在重复时更新给定条件下的数据框行

我的tkinter应用程序不会改变它正在加载的文件

Pandas/NumPy:当行值是行值的倍数时重置滚动平均值,最小尺寸

获取文本文件并创建CSV文件

用Arpeggio解析单行和多行注释

Kivy:如何给浮动按钮(FloatLayout)添加on_Release方法?