「オン」と「オフ」の 2 つの状態を持つ四角形のグリッドを使用しています。すべての「ON」コンポーネントを見つけるかなり単純な接続コンポーネントラベリングアルゴリズムがあります。通常、常にではありませんが、「ON」コンポーネントは 1 つだけです。
オン/オフ セルのマトリックス、コンポーネントのラベリング (おそらくセルのハッシュセットのリストとしてフォーマットされている)、およびラベリングが形成されてから変更されたセルのリストを入力として取り、出力するアルゴリズムを構築したいと考えています。新しいラベリング。明白な解決策は、ゼロから再計算することですが、これは効率的ではありません。一般に、変更されたセルのリストは小さくなります。
変更リストがオンになっているセルのみの場合、これは簡単に実行できます。
Groups G;
Foreach changed cell C:
Group U = emptygroup;
U.add(C);
Foreach Group S in G:
if (S contains a cell which is adjacent to C)
G.Remove(S);
U.UnionWith(S);
G.add(C);
ただし、変更にオフになっているセルが含まれている場合、どうすればよいかわかりません。すべての ON セルは、1 つのグループのメンバーでなければならないことに注意してください。したがって、1 つの解決策は、新しくオフになったセルに隣接する各セルを取得し、それらが互いに接続されているかどうかを確認することです (たとえば、パスファインディングを使用)。これにより、1 ～ 4 個の連続したグループが生成されます (セルがそのグループ内の唯一のセルであり、チェックする隣接セルが 0 である場合を除きます。この場合、0 個のグループが生成されます)。ただし、これはゼロから始めるよりも少しだけ良いにすぎません。なぜなら、通常 (常にではありませんが) これらの隣接する正方形を一緒に接続することは、隣接するグループを見つけるのと同じくらい難しいからです (誰かがそれを行うためのスマートな方法を提案していない限り)。また、変更されたセルがたくさんある場合は少し怖いです...ただし、通常はそうではないことは認めます。
文脈、なぜ私がこれをやっているのかを知りたがっている方のために:ぬりかべパズルのルールの 1 つは、連続する壁のグループは 1 つだけだということです。私が解決しようとしている問題を単純化して、速度を上げる (そしてパスファインディングで遊ぶ) ことは上記のとおりです。基本的には、以前のこのようなテストで得られた情報を無駄にすることなく、隣接する壁をチェックしたいと考えています。O(f(Δ)) が O(f(Δ)) (N はパズルのサイズで、Δ はアルゴリズムが最後に実行されてから行われた変更です)。
プロファイリングは、このアルゴリズムを改善すると実行時間に違いが生じることを示していますが、これは利益のためではなく楽しみのためのプロジェクトであるため、変更が何らかの影響を与えたかどうかを測定できることを除いて、それほど重要ではありません.
注: 現在のアルゴリズムの説明は省略しましたが、基本的には、最初に見つかった ON の正方形に対してスタックベースのフラッド フィルアルゴリズムを実行し、さらに ON の正方形があるかどうかを確認します (つまり、複数の正方形があることを意味します)。グループであり、調べる必要はありません)。
編集: 機能強化のアイデア: Yairchu と John Kugelman の提案は、私の頭の中でこの改善に具体化されました。これは、実際にはこの問題自体の解決策ではありませんが、コードのこの部分と他のいくつかのコードの実行を高速化する可能性があります。
現在のループ:
foreach (Square s in m.Neighbors[tmp.X][tmp.Y])
{
if (0 != ((byte)(s.RoomType) & match) && Retval.Add(s)) curStack.Push(s);
}
改善案:
foreach (Square s in m.NeighborsXX[tmp.X][tmp.Y])
{
if (Retval.Add(s)) curStack.Push(s);
}
これには、いくつかの m.NeighborsXX インスタンス (強化する必要のあるマッチの種類ごとに 1 つ) を維持し、正方形が変更されるたびにすべてを更新する必要があります。これが実際に役立つかどうかを確認するには、これをベンチマークする必要がありますが、速度を犠牲にしてメモリを交換する標準的なケースのようです。