部屋数をカウントするフラッドフィルアルゴリズム

Question

私は、壁で囲まれた空白の数を数えるフラッドフィルアルゴリズムを作成しようとしています。 2Dの文字列配列を使用しています。壁は「1」で表され、空白は空白です。 理想的には、アルゴリズムは、配列内のすべてのStringをチェックし、map [x] [y]のStringがnullでない任意のポイントを返し、壁で囲まれた空白の数を数えます。 しかし、分時には部屋数が非常に長くなり、どこが間違っているのかわかりません。

public static void floodFill(int x, int y, String oldChar, String newChar){ 

    x = 0; 
    y=0; 



    if (x < 0 || y < 0 || x > map.length || y > map[0].length){ 
     return; 
    } 

    if (map[x][y] != oldChar){ 
     return; 
    } 

    map[x][y] = newChar; 



    // Recursive calls 


     floodFill(x - 1, y, oldChar, newChar); 

     floodFill(x +1, y, oldChar, newChar); 

     floodFill(x, y-1, oldChar, newChar); 

     floodFill(x, y+1, oldChar, newChar); 


    } 

public static void getNumOfRooms(String map[][]){ 

    roomCount = -1; 

    for(x = 0; x < map.length; x++){ 
     for (y = 0; y < map[0].length; y++){ 
      if (map[x][y] == null){ 
       floodFill(x, y, null, "x"); 

       roomCount+=1; 
       System.out.println(map); 
      } 
    } 
} 

Answer 1

あなたのコードが、ここでいくつかのもの（一部は既にコメントで言及されている）してみてくださいするのが面倒：はいあなたは再帰呼び出し

ためmap[][]チェックの内側に欠けている

1. をあなたはこれを持っています：

   if (x < 0 || y < 0 || x > map.length || y > map[0].length) return; 
   

   しかし、あなたの再帰呼び出しが+2と-1の範囲外のインデックスにアクセスできるので、それは良くありません（役に立たなくても）。 >= map[0].lengthである必要があります。私は完全にし、代わりに使用している場合ことを削除します：

   if (x>    0) floodFill(x-1,y, oldChar, newChar); 
   if (x<map .length-1) floodFill(x+1,y, oldChar, newChar); 
   if (y>0)    floodFill(x,y-1, oldChar, newChar); 
   if (y<map[0].length-1) floodFill(x,y+1, oldChar, newChar); 
   

2. あなたは洪水充填何列ですか？

   は、私はJAVAコーダはので、私はこので間違ってないかもしれませんが、私はその後、C++アナロジーを使用する場合：

   public static void getNumOfRooms(String map[][]) 
   

   はそうあなたがローカルコピーにアクセスしているmap[][]の新しいローカルコピーを作成します。内部（配列コピーではないポインタを意味しない限り）。だから、おそらくローカルコピー内の値をチェックしているが、あなたの塗りつぶしではなく、元のマップにアクセスしている：

   public static void floodFill(int x, int y, String oldChar, String newChar) 
   

   だから、地元map[][]に変化はあなたがスペースでない部屋の数をカウントしている原因となりません。私はgetNumOfRoomsヘッダーからString map[][]オペランドを削除してそれを修正します。

3. あなたは

   ほとんどの部屋のレイアウトがどの部屋にも属していない外側の境界線のスペースを持っている背景を忘れています。だから、あなたの地図で一番外側の四角形をスキャンし、スペースが見つかった場合は、カウントする前に壁の文字か一時的な文字で塗りつぶして、それを部屋として数えないようにしてください。代わりに-1にカウンタを設定していますが、これは間違っています（外側にスペースがない場合はどうなりますか）。0にする必要があります。いくつかの文字列操作は、文字列の終端としてそれを使用すると、文字列にnull文字を使用していくつかのケースではnull文字

   を使用して

4. は危険なことができます。JAVAstringの場合もありますが、最初のマップ行は通常は外側のスペースなので、行はnullで始まります。この場合、一部の操作ではmap[0].lengthがゼロに変更される可能性があります。地図。私はASCIIのスペースを使う方がはるかに安全で、mapを印刷する方がはるかに簡単です。