查找可以放置在网格中的最大项目的算法

Question

二维空间中有一个 NXM 点网格。可以将一个项目放置在点 (x,y) 处，这样在 (x+2,y-2) 或 (x-2,y-2) 或 (x-2,y+2) 处不得有其他项目) 或 (x+2,y+2)。此外，网格中有几个点被卡住，即无法将元素放置在这些点上。

那么如何找到可以放置在网格中的最大项目数。

Answer 1

没有这些阻塞点的最佳填料是放置在柱子上

(a + 0), (a + 3), (a + 6), ..., (a + 3*n)

无论这些列中存在什么 block ，都无法进行改进。在列上存在 block 的位置 (x, y) 处，您可以在 (x+2, y-2) 和 (x-2, y-2) 上放置点。因此，查看所有列并尝试放置它们以最小化列上的 block 数。 (注意之前说的是maximize，我昨晚也睡了3h)

检查这个可以在 n*m 步内完成。