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

Question

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

例子:

0110
1111
1111 

解决方案是 2。

我知道可以用Bitmask DP解决；但我无法真正理解它 - 在玩了几个小时之后。它是如何运作的以及如何将其正式化？

Answer 1

我想指出的是，我们通过将顶点放在正方形的中心并在它们重叠时连接它们而得到的图不是无爪:

如果我们(在整个平面上)取一个​​ 2x2 正方形和四个对角重叠的 2x2 正方形中的三个，它们形成导出子图

•   •
 \ /
  •
 /
•

这是一个爪子，意味着包含这些方 block 的任何区域都对应于一个非爪子自由图。