algorithm - 算法 - 在二维网格中找到最近的空方格

Question

给定二维网格上的起始正方形 (y, x)，我想找到最接近它的空正方形。（注意：与起始方格相邻的 4 个方格应该被认为比最近的 4 个对角线方格更近。）

下图显示了我需要检查此网格上的以下单元格的顺序：

网格是有界的，但可能非常大。在实践中，起始坐标将随机位于网格周围。（所以，我认为担心网格边界之外的坐标并不重要......）

我可以使用什么算法以这种方式围绕圆圈进行迭代？

Answer 1

它可以通过 BFS（广度优先搜索）来解决。我们必须处理每个正方形两次。第一次我们访问与当前正方形共享边的仍然未访问的正方形，下次我们访问与当前正方形共享至少一个点的正方形（对角相邻的正方形）

我们可以使用两个不同的队列来确保在第二次处理正方形之前，从源到当前正方形距离相等的所有正方形都至少被处理过一次。:-)

平均运行时间：O(V*8) => O(V)。其中V是网格内的正方形数

Answer 2

一个简单的广度优先搜索就可以了。将每个要检查的邻居推到一个堆上，按距离优先。您可能可以使用曼哈顿距离 (dx + dy)，但如果不只是使用平方径向距离 (dx ² + dy ² )。每当您弹出一个项目时，它将是最近的。如果它是空的，你就找到了。否则将其邻居推到堆上并继续弹出。

我可能会使用正方形径向距离，只添加相邻的正方形（不是对角线）。稍后将考虑对角线，因为它们紧邻其他方格。您确实需要一种方法来跟踪已经考虑过哪些方格，这样您就不会再次添加它们。必须有一种巧妙的动态编程方法来跟踪这一点，而不必每次搜索时都清除一大块布尔值……但是说，一大块布尔值会做得很好。

Answer 3

如果网格的内容经常变化，请使用前面答案中描述的方法，即面包优先搜索。

如果您的网格内容很少更改并且曼哈顿距离对您的应用程序来说是可以的，我的建议是计算二值化网格的距离变换（如果为空，则为 0，否则为 1）距离变换对于曼哈顿距离非常简单，方式更复杂欧几里得距离）。此步骤的成本为 2*N*M（网格的元素数）。然后，对于每个请求，您可以以非常直接的方式访问邻域，即从起始单元格开始沿着最小距离的路径（如一些梯度下降），它将在最近的空单元格处停止。使用此算法进行搜索可能会更快，因为您不会以错误的方式查找超过 1 个单元格的空单元格。