algorithm - 将网格划分为矩形

<分区>

我有一个由 0 和 # 组成的网格。我想将所有 0 重新组合成矩形。最少需要多少个矩形？

示例:

在这个例子中，我们使用了 5 个矩形。还有其他解决方案，但 5 个矩形是覆盖所有 0 的最小值。

最佳答案

问题是NP-Hard并被称为经典的二维变体 bin-packing problem ，称为 2D-binpacking。
因此，这个问题没有已知的多项式解。

这已被广泛研究，这里有一个例子 article处理近似解决此问题的方法。

您也可以尝试使用 Genthic 算法或其他启发式方法来解决问题。

关于algorithm - 将网格划分为矩形，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/13827392/

相关文章：

algorithm - 如何在 Tictactoe 中实现 minimax