在二进制位图中选择非重叠2x2正方形的最大数量

Question

给定一个由1和0组成的矩形,如何找到1的非重叠2x2正方形的最大数量？

例:

0110
1111
1111 

解决方案是2.

我知道它可以用Bitmask DP解决; 但我真的无法抓住它 - 玩了几个小时之后.它是如何工作的以及如何正式化？

Answer 1

如果您构建一个图，其中每个节点代表一个由 1 组成的 2x2 正方形，并且两个节点之间存在一条边（如果它们重叠），那么现在的问题是：找到该图中的最大独立集。