2D グリッド上の開始正方形 (y、x) が与えられた場合、それに最も近い空の正方形を見つけたいと考えています。(注: 開始正方形に隣接する 4 つの正方形は、それに最も近い 4 つの斜めの正方形よりも近いと見なされます。)
次の図は、このグリッドの次のセルをチェックする必要がある順序を示しています。
グリッドは制限されていますが、非常に大きくなる可能性があります。実際には、開始座標はグリッドの周りにランダムに配置されます。(そのため、グリッドの境界外の座標について心配することはあまり重要ではないと思います....)
この方法で円の周りを反復するには、どのアルゴリズムを使用できますか?
単純な幅優先検索でそれができます。検査対象の各ネイバーを、距離の優先順位に従ってヒープにプッシュします。おそらくマンハッタン距離 (dx + dy) で逃げることができますが、半径距離の 2 乗 (dx 2 + dy 2 ) を使用するだけでは不十分です。アイテムをポップするたびに、最も近いアイテムになります。空の場合は、見つかりました。それ以外の場合は、隣接するものをヒープにプッシュし、ポップし続けます。
私はおそらく正方形の半径距離を使用し、隣接する正方形のみを追加します（対角線ではありません）。対角線は、他の正方形に直接隣接しているため、後で検討します。どの正方形が既に考慮されているかを追跡して、それらを再度追加しないようにする方法が必要です。検索するたびにブール値の大きなグリッドをクリアする必要なく、これを追跡する巧妙な動的プログラミング方法が必要です...しかし、そうは言っても、ブール値の大きなグリッドは非常にうまく機能します。
BFS（幅優先探索）で解けます。各正方形を 2 回処理する必要があります。最初に現在の正方形とエッジを共有するまだ訪問されていない正方形を訪問し、次に現在の正方形と少なくとも点を共有する正方形を訪問します (斜めに隣接する正方形)
2 つの異なるキューを使用して、正方形を 2 回目に処理する前に、ソースから現在の正方形までの距離が等しいすべての正方形を少なくとも 1 回処理することができます。:-)
平均実行時間: O(V*8) => O(V)。ここで、V はグリッド内の正方形の数です
グリッドの内容が頻繁に変更される場合は、前の回答で説明されている方法、つまりパン優先検索を使用します。
グリッドの内容がめったに変化せず、マンハッタン距離がアプリケーションに適している場合、2 値化されたグリッドの距離変換を計算することをお勧めします(空の場合は 0、それ以外の場合は 1) 距離変換はマンハッタン距離では非常に単純ですが、はるかに複雑です。ユークリッド距離の場合)。このステップは、2*N*M (グリッドの要素数) のコストで実行できます。次に、リクエストごとに、非常に簡単な方法で近隣を訪問できます。つまり、開始セルから始まる最小距離のパスをたどると (勾配降下のように)、最も近い空のセルで停止します。このアルゴリズムを使用すると、1 セル以上離れた空のセルを間違った方法で検索しないため、検索が非常に高速になる場合があります。