Flood-Fill-Algorithmus, der Räume zählt

Question

Ich versuche einen Flood-Fill-Algorithmus zu erstellen, der die Anzahl der von Wänden eingeschlossenen Leerstellen zählt. Ich verwende ein 2D-String-Array und die Wände werden durch "1" dargestellt und die leeren Leerzeichen sind null. Idealerweise sollte der Algorithmus jeden String im Array überprüfen und an jedem Punkt zurückgeben, an dem der String an der Positionskarte [x] [y] nicht null ist, und die Anzahl der von Wänden eingeschlossenen Leerstellen zählen. Aber in der Minute bekomme ich eine extrem lange Nummer für die Anzahl der Zimmer und nicht sicher, wo ich falsch liege.

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

Zu faul um Ihren Code zu versuchen, aber hier einige Dinge (einige sind bereits in den Kommentaren erwähnt):

1. Sie sind in map[][] prüft rekursive Aufrufe fehlende

   Ja Sie haben folgendes:

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

   Aber das ist nicht gut (sogar nutzlos), weil Ihre rekursiven Aufrufe dann Zugriff auf +2 und -1 Index außerhalb der Grenzen zugreifen können. Auch sollte >= map[0].length sein. Ich würde entfernen, wenn vollständig und stattdessen verwenden:

   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. Welche Array sind Sie Flut Füllung?

   Ich bin keine JAVA-Codierer so kann ich in diesen falsch sein, aber wenn ich C++ Analogie dann:

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

   neue lokale Kopie map[][] erstellen, so dass Sie die lokale Kopie zugreifen Inside (es sei denn, es bedeutet Zeiger nicht Array-Kopie). So werden Sie möglicherweise Werte in der lokalen Kopie Überprüfung aber Ihre Flußfüllen wird, um die Original-Karte Zugriff statt:

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

   Also keine Änderung in lokalen map[][] führen, dass Sie zählen Anzahl der Räume nicht Räume. Ich würde den String map[][] Operanden aus getNumOfRooms Header entfernen, um das zu beheben.

3. Sie vergessen den Hintergrund

   Die meisten Raumaufteilungen haben äußere Grenze Raum, der nicht in jedem Zimmer gehört. Sie sollten also das äußerste Rechteck in Ihrer Karte scannen und, falls ein Platz gefunden wurde, diesen entweder mit einem Wandzeichen oder einem temporären Charakter vor Ihren Zählräumen füllen, um es nicht als Raum zu zählen. Sie setzen den Zähler stattdessen auf -1, was falsch ist (was ist, wenn es kein äußeres Leerzeichen gibt), sollte es 0 sein.

4. mit null Charakter

   In einigen Fällen null Zeichen in Zeichenfolge mit gefährlich sein können, da einige String-Operationen als String-Terminator verwenden.Nicht sicher, ob es auch für Ihre JAVAstringstring ist aber wenn ja zum Beispiel in der ersten Kartenzeile ist normalerweise der Weltraum, so dass die Zeile mit null beginnen kann, die die map[0].length auf Null für einige Operationen ändern kann, die das Layout Ihres zerstören Karte. Ich würde ASCII-Raum verwenden stattdessen ist es viel sicherer und auch ist es viel einfacher, die map dann ausdrucken.