将较小的矩形组合成较大的矩形

Question

我有一个问题,我需要将小方块合并为更大的矩形.假设我有一个2D网格,填充随机1和0:

1 0 1 1 0
1 0 1 1 1
0 1 0 1 1
0 1 0 1 1
0 0 1 0 0

1代表填充的区域,我将它们绘制成屏幕方式为正方形.但是,对于这个问题,我需要先将它们匹配成矩形.在示例节目中,左上角的1​​是 - >

1
1

可以加入矩形.

我认为这应该足以解释我的需要.然而,优选的是,不在一个以上的矩形中使用特定的正方形.此外,它不一定是具有最少数量矩形的最佳情况,只是具有较少矩形的更好情况.如果它会使事情变得容易,也允许使用1x1矩形.

任何洞察我可以开始,甚至解决方案将不胜感激.

如果你想知道这个问题背后的原因,我正在为我正在研究的游戏开发一个关卡构建器,我想减少我的顶点数.我以为我会从方块开始,因为它们会很简单,但即使这样也让我难以置信.

感谢您花时间阅读!

Answer 1

一种简单的方法是寻找相邻的正方形并将它们变成矩形。为此，首先水平穿过网格并将水平相邻的方块连接在一起，然后垂直穿过网格并将垂直相邻的方块连接在一起。

考虑：

H = 水平矩形的一块

V = 一块垂直矩形

你原来的例子：

 1 0 1 1 0
 1 0 1 1 1
 0 1 0 1 1
 0 1 0 1 1
 0 0 1 0 0

会变成：

V 0 H H 0
V 0 H H H
0 V 0 H H
0 V 0 H H
0 0 1 0 0

这种方法不是最佳的，但如果可以在给定 2D 网格的情况下这样做，它将把正方形变成矩形。