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

Question

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

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

Answer 1

考虑一个更简单的一维问题：给定一个包含阻塞单元格的长度数组，n有多少种方法可以用这样的方法填充它，如果 1 处有 1，则和x处没有 1 。x - 2x + 2

请注意，这是一个冗余条件：如果我们有一个 1 at x，那么没有 1 就足够了x - 2（如果有一个 1 at x + 2，那将打破这个简化的条件）。

让dp[i, j] = number of ways to populate 1 .. i with points such that the last element is j.

我们有：

dp[i, 0] = dp[i - 1, 0] + dp[i - 1, 1] <- no 1 at i
dp[i, 1] = 2 * dp[i - 2, 0] <- we MUST have 0 at i - 2, but i - 1 can have whatever
=> if i is blocked dp[i, _] = dp[i - 1, _]

例子：

n = 3
brute force solutions:
000
010
100
001
110
011
=> 6
dp[0, 0] = 1 dp[0, 1] = 0
dp[1, 0] = 1 dp[1, 1] = 1
dp[2, 0] = 2 dp[2, 1] = 2
dp[3, 0] = 4 dp[3, 1] = 2
=> dp[3, 0] + dp[3, 1] = 6

同样可以用于您的问题。请注意，条件可以简化为“如果 (x - 2, y - 2) 和 (x + 2, y - 2) 处没有点，则 (x, y) 处可能有一个点”。然后只需迭代并填写您的 dp 矩阵O(lines*columns)。

Answer 2

我认为将网格视为圆环是说明性的，即侧面“环绕”（顶部->底部，左侧->右侧），以便您可以忽略边缘情况。当 N 和 M 很大时，无论如何这是一个很好的近似值。

在环面上，每个点必然会阻止其他两个点存在，但您可以重叠排除项，即一个点(x+2, y-2)是另一个点(x+2, y-2)。所以你可以达到的最大包装是 1/2。这可以通过交替列条来实现：2 个完整列、2 个空列、2 个完整列等。

我将保留极端情况（M 不是 4 的倍数）。

在不是圆环的网格上，您有两个考虑因素。首先，您可以将完整的列直接启动到网格的边缘。您也可以完全填充底部的两行（“底部”是最小的 y）。因此，您可以实现比 1/2 稍好一些的打包，但是当尺寸接近无穷大时，您仍然会得到 1/2。

Answer 3

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

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

只要这些列存在块，就无法进行改进。如果列上存在块，在 (x, y) 处，您可以在 (x+2, y-2) 和 (x-2, y-2) 上放置点。因此，查看所有列并尝试放置它们以最小化列上的块数。（注意这之前说的是最大化。我昨晚也睡了 3 小时）

检查这可以在 n*m 步骤中完成。