2

注:これは、ロジックの問題などが好きな人にとっては難しい問題です。

高さH、幅Wの長方形の2次元グリッドについて考えてみます。グリッド上のすべてのスペースには、またはのいずれかの値があり0 1ます2。最初は、グリッド上のすべてのスペースは、です0。ただし、最初は。である4つのエッジのそれぞれに沿ったスペースは除きます2

次に、隣接する(水平または垂直)グリッドスペースの任意のパスを検討します。パスはa2で始まり、別ので終わります2。パスに沿ったすべてのスペースは1です。

0パスは、グリッドをスペースの2つの「セクター」に分割します。0不特定のスペースにあるオブジェクトがあります。オブジェクトを含まない「セクター」は、完全に。で埋める必要があります2

グリッド内の値に対応する値( 、、、または)の配列(リスト)を指定して、上から下へ、次に左から右へと進む2必要があるスペースを決定するアルゴリズムを定義します。つまり、配列のインデックス0の要素には、グリッドの左上のスペースの値(最初はa )が含まれています。インデックス1の要素には、左の列、上から2番目などにあるグリッド内のスペースの値が含まれます。インデックスHの要素には、一番上の行にあるが左から2番目のグリッド内のスペースの値が含まれています。00122

アルゴリズムが終了し、空の「セクター」がsで完全に満たさ2れると、同じプロセスを再度実行するには、同じアルゴリズムで十分である必要があります。2回目(およびそれ以降)のパスは、のスペースを横切っ2て、から別のに描画されますが、他のsに囲まれているsはパスに触れることができないため、「グリッド」は小さくなります(パスはのスペースに沿って。20220

これを理解してくれた人に感謝します。これは特定のプログラミング言語である必要はありません。実際、擬似コードまたは英語だけで十分です。再度、感謝します!ご不明な点がございましたら、コメントを残していただければ、何を指定する必要があるかをお知らせします。

4

1 に答える 1

3

私には、基本的なフラッド フィルアルゴリズムで作業が完了するようです。

  • 最初に見つけた配列をスキャンし、0そこから塗りつぶしを開始し、0領域を他の数字で塗りつぶし3ます。これにより、「セクター」の1つにラベルが付けられます。
  • それが完了したら、 を再度スキャンし、0そこからフラッド フィルを行い、今度は をフィルし4ます。
  • 両方の塗りつぶし中に、オブジェクトが見つかったかどうかを確認できます。途中で見つけた塗りつぶしが何であれ、その数を追跡します。
  • 両方の塗りつぶしが完了したら、どの番号の領域にオブジェクトが含まれているかを確認します。その領域を再びフラッドで塗りつぶし、今度はその領域に戻り0ます。
  • 他の番号の領域を で塗りつぶす2と完了です。

0これは、互いに切断されているセクターが2 つある限り、どのグリッド構成でも機能します。したがって、同じアルゴリズムを何度でも再適用しても問題ありません。

編集:フラッドフィルを1つか2つ節約するためのマイナーな調整-

  • 最初の塗りつぶしでオブジェクトが見つからない場合は、他のセクターにオブジェクトがあると想定できるため、現在の数値を再入力し、他のセクターをそのままにし2ておきます (既に0塗りつぶされているため)。
  • または、最初の塗りつぶしでオブジェクトを見つけた場合は、他のセクターを で直接塗りつぶし2最初のセクターを で再度塗りつぶすことができます0
于 2010-05-15T21:23:37.290 に答える