5

ユーザーが指定した初期座標を取得し、文字をチェックしてから、必要に応じて変更する塗りつぶしメソッドを作成しようとしています。その後、隣接する正方形をチェックし、プロセスを繰り返します。いくつかの調査の後、フラッドフィルアルゴリズムに出会い、それを試した後(動作しますが、250 x 250 文字の配列の最大要件を満たすことができません)。

私の元のフラッド フィル アルゴリズムは次のとおりです。

public static void fillArea (int x, int y, char original, char fill){

   if (picture[y-1][x-1] != original){
      return;
   }
   picture[y-1][x-1] = fill;
   fillArea (x-1, y, original, fill);
   fillArea (x+1, y, original, fill);
   fillArea (x, y-1, original, fill);
   fillArea (x, y+1, original, fill);

   return;
}

テストの後、ウィキペディアで説明されているように Queue メソッドを試し始めました。この質問は、同様の問題に関して以前に尋ねられました。これまでのところ、次のコードを思いつきました。

public static void fillArea (int x, int y, char original, char fill){
  if (x != 0)
     x--;
  if (y!= 0)
     y--;
  Queue<Point> queue = new LinkedList<Point>();
  if (picture[y][x] != original){
      return;
  }
  queue.add(new Point(x, y));

  while (!queue.isEmpty()){
      Point p = queue.remove();
      if (picture[p.y][p.x] == original){
         picture[p.y][p.x] = fill;
         queue.add(new Point(p.x-1, p.y));
         queue.add(new Point(p.x+1, p.y));
         queue.add(new Point(p.x, p.y-1));
         queue.add(new Point(p.x, p.y+1));
      }
   }

   return;
}

最初の再帰的な方法は小さい値に対しては機能しましたが、配列が大きくなりすぎると機能しません。ただし、2 番目の方法では、Queues の経験が浅いために識別できないある種の無限ループに陥ります。最初のコード サンプルをより大きなサンプルで動作するように最適化するか、2 番目のコード サンプルを修正して結果が得られるようにするにはどうすればよいですか? これら2つのいずれかをコーディングする方法、または私が間違っていることを誰かが説明できますか?

ありがとう！

編集: 2 番目のコードで無限ループ エラーを見つけることができました (修正されました) が、キュー ベースの方法では完全な領域が埋められません。実際、再帰ベースの方法よりも領域が少なくなります。EDIT 2:正方配列で機能するようになりました。長方形配列でも機能することを確認するにはどうすればよいですか (2 番目の方法)。

4

2 に答える 2

1

すべきではない

if (picture[p.y][p.x] == original){
     picture[p.y-1][p.x-1] = fill;

なれ

if (picture[p.y][p.x] == original){
     picture[p.y][p.x] = fill;

キュー内-アプローチ？

于 2012-09-23T12:36:52.287 に答える
1

参考までに、処理している配列の周囲にバッファ境界線を追加することで、質問を修正しました。たとえば、入力する配列が

000
000
000

になりました

   #####
   #000#
   #000#
   #000#
   #####

処理される前に。

于 2012-09-23T12:42:27.200 に答える