Array/Matrix auswerten.

[JKostiK]

Hallo!
Hat jemand eine Idee zu folgendem Problem:

Ich habe ein 5x5 Array...

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

...nun möchte ich als Ergebnis die Anzahl der Einsen aus dem grösten Block bestimmen. In diesem Fall sind es drei.
Ein Block besteht aus benachbarten (nicht diagonal) Einsen. Aus dem Beispiel: Der obere Block hat drei, der nächste zwei, dann eins und noch eins... insgesammt sind es vier Blöcke.

Ich habe keinen Schimmer wie ich die Blöcke bestimme.

Hiiiiilfe! DANKE!

PS: Dies möchte ich in natürlich in Java realisieren.

 

[Marco13]

Durch den Array durchlaufen, und sobald eine 1 gefunden wird... etwa so

int countOnes(int a[][], int x, int y) // Array, und die Position, an der die 1 steht
{
    if (x,y außerhalb der arraygrenzen) return 0;
    if (a[x][y]!=1) return 0;
    int count = 1;
    a[x][y] = 0; // damit man nichts doppelt zählt
    count += countOnes(a, x-1, y);
    count += countOnes(a, x+1, y);
    count += countOnes(a, x, y-1);
    count += countOnes(a, x, y+1);
    return count;
}

 

[JKostiK]

:toll: Suuuper! Habe es zum Laufen gebracht.
:meld: Es fehlt mir aber trotzdem das Verständnis wie das Ganze im Detail funktioniert.
...Es wird in der Funktion die selbe Funktion mehrmals aufgerufen. Müsste das nicht eigentlich eine Endlosschleife ergeben? ???:L Bitte hilf mir diese Wissenslücke zu schliessen.

 

[Quaxli]

Was Dir Marco13 gezeigt hat, nennt sich rekursiver Methodenaufruf. Eine Methode, die sich selbst wieder aufruft. Google mal mit dem Stichwort "Rekursion", da findest Du bestimmt einige Definitionen dazu.

Wikipedia - Rekursion

 

[Marco13]

Ja, in anbetracht der fortgeschrittenen Zeit gestern war ich etwas sparsam mit erklärungen - aber wenn du den Code mal per Hand(!) an einem ca. 4*4 felder Großen Beispiel nachvollziehst, wird er sich glaubich erschließen.

Das wichtige (zum Verhindern der Endlos"schleife" (eigentlich: Endlosrekursion)) ist, dass es einen "Basisfall" gibt, der irgendwann erreicht wird. Hier ist der Basisfall der, dass man entweder ausßerhalb der Arraygrenzen liegt, oder ein Feld mit einer 0 gefunden hat. Die 4 Aufrufe bewirken jeweils, dass man "einen Schritt weiter in eine Bestimmte Richtung läuft". Und damit kommt man garantiert irgendwann an eine Arraygrenze, d.h. das ganze hört garantiert irgendwann mal auf.

Ein leicht nachvollziehbares Beispiel für eine Rekursion ist die rekursive Berechnung der Fakultäts-Funktion - kannst mal danach suchen, falls du nicht schon drüber gestolpert bist.

 

[Guest]

Alles klar, DANKE!
Nur noch eine Kleinigkeit, diese Zeile verstehe ich nicht "int count = 1;". Wird da nicht die Variable "count" bei jedem erneuten Funktionsaufruf wieder auf 1 zurückgesetzt? :bahnhof: Es funktioniert zwar... aber wie?

 

[Drake]

Hallo

nimm dir ein Blatt Papier und einen Stifft, die Farbe sei dir überlassen, und 'spiele' das anhand einiger Testdaten einfach durch.
Um es zu verstehen schau dir vielleicht wirklich den genannten Link zur Rekursion an und gehe den Algo einfach mit den jeweils benutzen Werten und deren Ergebniss durch. Alles andere bringt dir nichts, jedenfalls wenn du wissen möchtest wie es funktioniert und nich einfach eine Antwort haben willst die du auswendig lernen kannst.
Ja, du musst womöglich ein klein wenig Zeit investieren, aber in Relation gesetzt zu der Zeit die du für suchen und warten bereit warst zu opfern sollte es nicht der Rede Wert sein.

mfg
Drake