algorithm - 最大平方堆积的图算法

Question

我有一个连接正方形的区域（左侧的 img），并且想要找到可以适合该区域的“双”正方形的最大数量（右侧的 img）。

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

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

Answer 1

引理 1：

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

证明：

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

算法：

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