フラッドフィルアルゴリズムの説明

塗りつぶしは、主に多次元配列内の特定のノードに接続された境界領域を決定するために使用されるアルゴリズムです。これは、ペイントプログラムのバケットツールによく似ています。

アルゴリズムの最もアプローチされた実装はスタックベースの再帰関数であり、それが次に説明するものです。

それはどのように機能しますか?

問題は非常に単純で、通常は次の手順に従います。

  1. 出発点の位置を取ります。
  2. 4方向(N、S、W、E)または8方向(N、S、W、E、NW、NE、SW、SE)のどちらに行くかを決定します。
  3. 代替色とターゲット色を選択します。
  4. それらの方向に移動します。
  5. あなたが着地したタイルがターゲットである場合、選択した色でそれを取り替えます。
  6. 境界内のいたるところにいるまで、4と5を繰り返します。

例として次の配列を取り上げましょう。

代替テキスト

赤い四角が出発点で、灰色の四角がいわゆる壁です。

詳細については、関数を説明するコードを次に示します。

int wall = -1; void flood_fill(int pos_x, int pos_y, int target_color, int color) 

上で見たように、私の出発点は(4,4)です。開始座標x = 4およびy = 4の関数を呼び出した後、その場で壁や色がないかどうかの確認を開始できます。それが有効な場合は、スポットを1つの「色」でマークし、他の隣接する正方形のチェックを開始します。

南に行くと、ポイント(5,4)に到達し、関数が再び実行されます。

運動の問題

新しく学んだアルゴリズムを使用して(またはそれ以上の)問題を解決することが、概念を完全に理解するための最良の方法であると常に考えていました。

だからここに1つあります:

ステートメント:

二次元配列では、n個の「島」が与えられます。島の最大の面積と対応する島の番号を見つけてみてください。0は水を示し、1からnまでのその他のxは、島xに対応する表面から1つの正方形を示します。

入力

  • n-島の数。
  • l、c-行列の次元。
  • 次のl行、行列のl番目の行を示すc数。

出力

  • i-最大の面積を持つ島の番号。
  • A - i番目の島の面積。

例:

次の入力があります。

2 4 4 0 0 0 1 0 0 1 1 0 0 0 2 2 2 2 2

あなたは島番号を取得します。5つの正方形の面積を持つ最大の島として2。

ヒント

問題は非常に簡単ですが、ここにいくつかのヒントがあります。

1. Use the flood-fill algorithm whenever you encounter a new island. 2. As opposed to the sample code, you should go through the area of the island and not on the ocean (0 tiles).