0

我得到了一个有两点的网格。我想计算每个点可以在另一个之前达到的平方数量。目前我实现了一个 FloodFill-Algoritm，它可以计算一个点可以达到的正方形数量。

如何更改该算法以同时或至少一个接一个地对两个点进行“洪水”？

4

1 回答 1

2

“每个点都可以先于另一个点到达”是什么意思？

在我看来，您需要进行 BF 搜索。像这样使用 FIFO 队列：

设 p1 和 p2 为两点的位置。

令 f 为队列中的第一个元素， l 为最后一个元素。最初 f = 0，l = 1。令 Q 为队列。

Q[f] = p1
Q[l] = p2
while ( f <= l )
{
   poz = Q[f];
   ++f;

   for each neighbour poz' of poz
      if poz' hasn't been marked yet
      {
         mark poz'
         add poz' to Q: Q[++l] = poz
      }
}

Q 需要是网格的大小（行 x 列）。您可以使用两个矩阵：一个是 p1 可以到达的位置，另一个是 p2 可以到达的位置，或者您可以使用一个矩阵并用正数标记 p1 到达的正方形，用负数标记 p2 到达的正方形。如果您对他们相遇的地方感兴趣，您只需要检查是否要从负值（poz 负值和 poz' 正值）标记一个正值或反之。这基本上会轮流进行泛洪：从 p1 泛洪一个方格，然后从 p2 泛洪，然后从 p1 泛洪，然后从 p2 泛洪，依此类推。

于 2010-02-18T13:34:03.327 回答