0

2点のグリッドを取得しました。各ポイントが他のポイントよりも先に到達できる正方形の量を計算したいと思います。現在、私は FloodFill-Algoritm を実装しています。これは、1 つのポイントが到達できる正方形の量を計算できます。

そのアルゴリズムを変更して、両方のポイントに対して同時に、または少なくとも 1 つずつ「フラッディング」を行うにはどうすればよいですか?

4

1 に答える 1

2

「各ポイントが他のポイントより先に到達できる」とはどういう意味ですか?

BF検索が必要なようです。次のように FIFO キューを使用します。

p1 と p2 を 2 点の位置とします。

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 列) である必要があります。2 つの行列を使用できます。1 つは p1 が到達できる位置、もう 1 つは p2 が到達できる位置です。または、1 つの行列を使用して、p1 が到達する四角形を正の数でマークし、p2 が到達する四角形を負数でマークすることができます。それらがどこで出会うかに興味がある場合は、負の値から正の値 (poz 負および poz' 正) をマークしようとしているのか、またはその逆なのかを確認する必要があります。これは基本的にフラッディングを順番に行います: p1 から 1 マス、次に p2 から、次に p1 から、次に p2 からというようにフラッドします。

于 2010-02-18T13:34:03.327 に答える