计算网格中标记节点 k 距离内的节点

Question

我正在尝试解决编码挑战，但我的解决方案性能不是很好，我正在寻找有关如何改进算法的意见或建议。

谜题如下：

给你一个代表果园的单元格网格，每个单元格可以是空地 (0) 或果树 (1)。一位农民希望知道果园内距离所有果树 k 距离内有多少个空点。

使用出租车几何形状计算距离，例如：

k = 1

[1, 0]
[0, 0]

the answer is 2 as only the bottom right spot is >k distance from all trees.

我的解决方案是这样的：

1. 循环网格并存储所有树位置
2. 从第一个树位置开始进行 BFS 并存储所有空点，直到我们到达超出 k 距离的邻居
3. 从下一个树位置开始进行 BFS 并存储空点的交集
4. 重复步骤 3，直到迭代完所有树位置
5. 返回所有交叉点后剩余的空点数量

我发现对于 k 值较大的大型网格，我的算法变得非常慢，因为我最终多次检查网格中的每个点。经过一些研究，我找到了一些类似问题的解决方案，建议采用两个最极端的目标节点，然后仅比较与它们的距离：

• https://www.codingninjas.com/codestudio/problem-details/count-nodes-within-k-distance_992849
• https://www.geeksforgeeks.org/count-nodes-within-k-distance-from-all-nodes-in-a-set/

然而，鉴于某些输入，这对我的挑战不起作用，如下所示：

k = 4

[0, 0, 0, 1]
[0, 1, 0, 0]
[0, 0, 0, 0]
[1, 0, 0, 0]
[0, 0, 0, 0]

使用极端节点方法，即使右下角的空点距中间树 5 距离，也会对其进行计数。

有人能指出我一种更有效的方法吗？我对这些类型的问题仍然很陌生，所以我发现很难看到我应该采取的下一步。

Answer 1

由于网格和距离结构，这个问题有一个简单的线性时间解决方案。给定一棵坐标为 (a, b) 的果树，考虑围绕其周围距离为 k 的框的 4 条对角线。向下和向右的对角线具有恒定值 x + y，而向下和向左的对角线具有恒定值 x - y。

点 (x, y) 位于框内（因此位于 (a, b) 的距离 k 内）当且仅当：

1. a + b - k <= x + y <= a + b + k，并且
2. a - b - k <= x - y <= a - b + k

因此我们可以迭代我们的果树 (a, b) 来找到四个数字：

• First_max = max(a + b - k); First_min = min(a + b + k);
• Second_max = max(a - b - k); Second_min = min(a - b + k);

其中最小值和最大值适用于所有果树。然后，迭代空单元格（或者做一些数学计算并减去果树计数，如果您的网格很大），计算有多少个空点 (x,y) 满足

1. 第一个最大 <= x + y <= 第一个最小，并且
2. 第二个最大 <= x - y <= 第二个最小。

这段 Python 代码（以过程风格编写）说明了这个想法。每个边界框的每条对角线正好截断平面的一半，因此这相当于平行半平面的交集：

fruit_trees = [(a, b) for a in range(len(grid))
                      for b in range(len(grid[0]))
                      if grid[a][b] == 1]

northwest_half_plane = -infinity
southeast_half_plane = infinity

southwest_half_plane = -infinity
northeast_half_plane = infinity

for a, b in fruit_trees:
    northwest_half_plane = max(northwest_half_plane, a - b - k)
    southeast_half_plane = min(southeast_half_plane, a - b + k)

    southwest_half_plane = max(southwest_half_plane, a + b - k)
    northeast_half_plane = min(northeast_half_plane, a + b + k)

count = 0
for x in range(len(grid)):
    for y in range(len(grid[0])):
        if grid[x][y] == 0:
            if (northwest_half_plane <= x - y <= southeast_half_plane
            and southwest_half_plane <= x + y <= northeast_half_plane):
                count += 1

print(count)

关于代码的一些注释：从技术上讲，数组坐标是从图片的笛卡尔坐标旋转四分之一圈，但这在这里并不重要。代码故意省略了某些看似显而易见的“优化”，原因有两个：1. 最佳优化取决于果树和网格的输入格式，2. 解决方案虽然概念简单，但也很简单阅读、编写时正确并不容易，重要的是代码“明显正确”。如果性能需要，可以稍后添加“如果下限超过上限则提前退出并返回 0”之类的内容。