在无限网格上找到最近的空点

Question

这是我在面试中被问到的一个问题。它涉及到一个2D网格由无限大小的空的和已占用的位置(如果你愿意，也可以是0和1)组成。输入包含被占用点的坐标，它要求我返回最近的空点对于每一个被占用的位置。在遍历过程中，您可以遍历被占用的点。这是一个自由格式的编码挑战，一开始就不涉及方法签名。

我在算法方面有经验，以前解决过类似的问题，寻找最近的位置问题通常涉及BFS在给定的图上。然而，网格是无限大小事情变得复杂了，现在我知道我无法将整个网格存储在矩阵结构中。尽管如此，我最终还是选择了BFS方法。这时出现了一个问题，即如何检查当前位置是否被占用。为每个访问节点遍历输入中的每个点似乎不是一个很好的选择，因为它太慢了。所以我建议，如果我能以某种方式将被占用的点映射到哈希映射中，那么检查操作就可以在常数时间内完成。面试官告诉我假设我有一个坐标的哈希函数，我的最终解决方案是这样的:

for each occupied spot in the input
create a queue and push the current spot into the queue
while queue is not empty
get the first element from the queue
if the spot is not occupied and not marked
add the spot into result list and break the while loop
else if spot is not marked
push its neighbors into queue and mark it

外部for循环接受O(n)输入中每个点的时间。BFS算法运行在O(v + e)，面试官建议可以表示为O(n)。在最坏的情况下，它访问所有被占用的位置，所以它确实是O(n)。我的最终算法运行在O(n^2).

正如你所预料的，我面试失败了，否则我不会发布这个问题。你能指出我的错误吗?我觉得面试进行得很顺利，在网上找不到关于如何在无限网格上解决问题的任何内容。也许我应该先说明如何存储一个无限网格，但当时我想不起来。

Answer 1

我猜他们想让你做的是绕一个螺旋，中心从每个已知的占位点开始。比如:

Distance = 1;
foreach(occupiedSpace)
{
occupied = true; // my own position is occupied by definition
While (!occupied) // loop in a spiral and check for an open space
{
for(possibleXPosition = -1* distance + occupiedSpace.x to distance + occupiedSpace.x)
for(possibleYPosition = (-1)+distance + occupiedSpace.y to distance + occupiedSpace.y ){
occupied = check( array[possibleXPosition, possibleYPosition])
if(!occupied){ 
output.print(closest position to (occupiedSpace is possibleXPosition, 
possibleYPosition)
}
}

distance++;
}}

这里有一些真实的实现:从原点出发的离散二维网格上的向外螺旋迭代算法

Answer 2

看LeetCode #286墙和门。这是BFS解决方案的一个变体。

但是，在初始化队列时不是添加gate，而是将未占用的队列旁边的已占用的队列添加到队列中。你会在每一个地方同时开始BFS。

希望这个提示有帮助。