最有效地将特定数量的等大小矩形打包到带有障碍物的网格上

Packing a specific number of equally sized rectangles on a grid with obstacles most effectively

提问人：Crater Hater 提问时间：7/11/2023 更新时间：7/15/2023 访问量：32

问：

我正在尝试找到一种算法，可以将特定数量的相同大小的矩形放置在有障碍物的网格中。矩形不应重叠，并且到给定起始位置的总距离应最小。

enter image description here enter image description here

红色是障碍物，橙色是放置的矩形（在本例中为 9）。绿色点是锚点，所有橙色矩形到该点的总距离应该最小。

算法 与语言无关 的动态规划

评论

1赞 templatetypedef 7/12/2023
在您的示例中，没有选择对角线左上角和对角线左下角的点，这是有原因的吗？
0赞 Crater Hater 7/12/2023
不，没有。这些确实可能更接近，具体取决于您在矩形上测量它的位置。
0赞 templatetypedef 7/13/2023
矩形是否必须与网格和 1x1 对齐？
0赞 Aldert 10/26/2023
你是否理解答案，如果是，请接受。

答：

0赞 Aldert 7/15/2023 #1

我会把问题稍微扭转一下：我们有一个正方形网格，需要将其与你的障碍物叠加和定位。如果我们将障碍物在网格上水平或垂直移动一个方格，我们就可以涵盖所有可能的选项（否则我们将重复相同的情况）。

假设大梁是 10 毫米的网格。当我们开始向左移动时，我们只需要测试障碍物边界的位置。(0, -5, -6, -7)

enter image description here

在位置 0，我们有 16 个完整的正方形（上图）

在位置 -5，我们有 11 个完整的正方形（下图）

enter image description here

在位置 -6，我们有 11 个完整的正方形，在位置 -7，我们有 14 个完整的正方形。

enter image description here enter image description here

我们可以得出结论，位置 0 是水平对齐的最佳位置。

我们可以在上面重复这个过程进行垂直对齐。我们得出结论 （0， -5） 是我们的最佳优化位置，有 19 个正方形。

enter image description here

上一个：从另一个文件中的文件中搜索文本模式

下一个：合并两棵树的算法