Zusammenhängende Werte in 2-dim. Array finden und zählen

[rhino]

Hallo Leute,

ich programmiere gerade ein kleines puzzle spielchen für Android Geräte und stehe vor einem Problem.

Ich habe ein Spielfeld Array mit 12x10 Feldern. In diesem Array können Spielsteine liegen, die durch 1en dargestellt werden. Befindet sich an einer Stelle kein Spielstein, so trägt das Feld den Wert 0.

Nun geht es darum festzustellen, wieviele zusammenhängende Flächen es gibt, die mit 1en gefüllt sind.

1 1 1 0 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0

In diesem Fall gibt es eine Fläche..

1 1 1 0 0 0 0 0 0 0 0 0
1 1 0 0 0 0 1 1 1 1 1 0
1 0 0 0 0 0 0 0 0 1 1 0
0 0 0 0 0 0 0 0 0 1 1 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0

In diesem Fall, sollen zwei Flächen gezählt werden, usw.


Hat jemand eine Idee wie man das bewerkstelligen könnte?
Danke

 

[Gast2]

Du gehst dein Spielfeld Feld für Feld durch. Wenn du eine 1 findest machst du folgendes:
1) Prüfen ob die 1 schonmal besucht wurde
2) Wenn ja, dann mit nächstem Feld weitermachen
3) Wenn nein, dann gehst du rekursiv nach links/unten/rechts/oben, suchst alle angrenzenden 1er und markierst die als besucht.
3.1) Flächenzähler um eins erhöhen.

 

[langhaar!]

Das Prüfen und Markieren entspricht einem Floodfill-Algorithmus. (jede Fläche wird mit einer neuen 'Farbe' entsprechend dem Flächenzähler gefüllt)

Hier eine iterative Version (kopiert von Wikipedia):

fill(x, y, alteFarbe, neueFarbe) {
 
   stack.push(x, y);
 
   while(stack.isNotEmpty) {
      (x, y) = stack.pop;
 
      if (getPixel(x, y) == alteFarbe) {     
         markierePixel(x, y, neueFarbe);
 
         stack.push(x, y + 1);
         stack.push(x, y - 1);
         stack.push(x + 1, y);
         stack.push(x - 1, y);
      }
   }
   return;
}

 

[rhino]

Danke, hat bestens geklappt