algorithm - 双正方形最大堆积图算法

Question

我有一个由相连方 block 组成的区域(左边的 img)，我想找到可以放入该区域(右边的 img)中的“双”方 block 的最大数量。

我的方法是将原始区域表示为图形，其中每个正方形代表一个顶点，通过边连接到下方、上方、左侧和/或右侧的正方形。

我认为这可以通过使用 BFS 算法来完成，检查每个顶点并应用颜色。但我也觉得它可以用动态规划来完成......我需要一些帮助!

Answer 1

引理 1:

如果我们将正方形视为图中的顶点，由于其空间结构，该图是二分图。 将每个顶点的边链接到其所有邻域顶点。

证明:

如果我们把每个方 block 涂成白色或黑色，就可以形成没有两个黑色相邻，也没有两个白色相邻，所以图中的边只会在一黑一白之间。

算法:

构造二分图后，可以找到二分图的最大匹配，最大匹配的值就是答案。您可以使用匈牙利算法或更快的 Hopcroft-Karp 算法来计算答案。