最近的空闲格子的二维网格数据结构

Question

考虑一个2000x2000的二维布尔数组。其中有10万个元素为true，其余元素为false。

给定一个单元格(x1,y1)，我们需要找到最近的false单元格(x2,y2)(按曼哈顿距离：abs(x1-x2)+abs(y1-y2))。

一种方法是：

for (int dist = 0; true; dist++)
    for ((x2,y2) in all cells dist away from (x1,y1))
        if (!array[x2,y2])
            return (x2,y2);

最坏情况下，我们需要在找到空闲单元格之前遍历100,000个单元格。

除了使用2D数组，还有什么数据结构可以让我们更快地执行此搜索吗？

- Andrew Tomazos

---

数组会被更新吗？你只会进行多次搜索吗？ - Petar Minchev

数组是常量，而你会有很多关于它的查询吗？还是每个数组问题只有一个查询？如果你只使用一次，那么创建聪明的数据结构实际上没有任何意义。 - amit

抱歉，是的，数据会改变 - 一旦找到一个单元格，它就被标记为真。 - Andrew Tomazos

Answer 1

如果数据是不变的且您需要对其进行多次查询：
您可能希望使用k-d树，并查找最近的邻居。为每个元素插入(i,j)，使得arr[i][j] = false。标准的k-d树使用欧几里得距离，但我认为可以修改它以使用曼哈顿距离。

如果数据仅用于一个查询：
您将需要至少Omega(n*m)个操作来读取数据并将其插入任何数据结构中-没有必要这样做-所建议的解决方案只会在构建任何数据结构时表现出色。

- amit

---

典型的kd树算法由于三角不等式可以处理任何度量。 - salva

Answer 2

您可能会对区域四叉树感兴趣。在这里，最初将整个图像建模为根，因为假设图像包含所有的 0。然后当设置了特定像素时，首先将图像分成 4 个象限，而不包括像素的 3 个象限留作叶子节点。剩余的象限再次被细分，以此类推，直到得到 4 个点叶子节点，其中一个被设置。这种表示法有助于在搜索过程中排除整个区域，从而可以将搜索时间优化为 O(log n)。

- PermanentGuest