Array/Matrix auswerten...

Dear visitor, welcome to Coder Forum. If this is your first visit here, please read the Help. It explains in detail how this page works. To use all features of this page, you should consider registering. Please use the registration form, to register here or read more information about the registration process. If you are already registered, please login here.

JKostiK

Beginner

Posts: 2

Wednesday, June 27th 2007, 11:08pm

Array/Matrix auswerten...

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.

truespin

Professional

Posts: 378

Thursday, June 28th 2007, 7:26am

hm... kannst du das mit deine blöcken evtl nochmal ne bisschen genauer erklären? steh da gerade auf der leitung... kann natürlich auch an der uhrzeit liegen

thx, truespin

Marcus Gnaß

Professional

Posts: 217

Thursday, June 28th 2007, 11:11am

Re: Array/Matrix auswerten...

Ein Block soll wohl ein Viereck sein in dem alle Einsen über Kanten verbunden sind. also nebeneinander oder untereinander liegen. Folgendes ist also ein Block:

1 1
0 1

Verbindungen über Ecken (also diagonal aneinandergrenzende Einsen) reichen wohl nicht aus:

0 1
1 0

Dann dürfte also auch folgendes ein Block sein:

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

Hab ich das richtig verstanden?

truespin

Professional

Posts: 378

Thursday, June 28th 2007, 11:57am

ahh und jetzt willst du wohl wissen wie viele einsen in einem block sind? liege ich da richtig?? :?:

dann gehe doch durch dein array mit ner for-schleife durch und überprüfe jeden index ob 0 oder 1. wenn 1 dann nen counter hochzählen...

thx, truespin

*edit:

ein block besteht dann mindestens aus zwei 1 oder?

mad

Professional

Posts: 662

Thursday, June 28th 2007, 12:55pm

Nein, ein block besteht aus vier elementen. Und er will den Block haben, indem die meisten einsen sins Und er möchte die Anzahl dieser haben.

Ein Bild zu Veranschaulichung...
Zumindest denke ich, dass er es so meint, ne Idee für nen Algo hab ich aber noch nicht

cya

mad has attached the following image:

BennyBunny

Master

Posts: 966

Thursday, June 28th 2007, 2:44pm

Das ein block aus vier Elementen besteht steht nirgends....

Latest blogs: Oracle übernimmt Sun, Java SE 6 Update 12 verfügbar, Java 1.6.0 Update 10

mad

Professional

Posts: 662

Thursday, June 28th 2007, 6:24pm

Das stimmt, allerdings hat er oben den BLock mit der größten Anzahl beschrieben und das ist ein Block mit 3 Einsen. Die Beschreibung deutet auf 4-er Blöcke hin (auch wegen den beiden anderen beschriebenen Blöcken)

Idee für Algorithmus: Alle Blöcke rausfinden, dann jeden Block durchlaufen, wie truespin schon beschrieben hat.
Sollte aber auch irgendwie anders machbar sein, aber vielleicht kannst du ja erstmal was dazu sagen, ob wir die Block-Sache richtig verstanden haben oder nicht...

cya

BennyBunny

Master

Posts: 966

Thursday, June 28th 2007, 6:30pm

Ne, ich denke, dass mit ienem Block gemeint ist ein Verbund aus Einsen, die horizontal und vertikal verbunden sind. so les ich das zumindest raus aus der Problemstellung:

Aber zum Problem: Vielleicht solltest du einfach erst jede reihe und dann jede spalte durchlaufen, wenn du eine eins gefunden hast, dann merkst du dir die stelle, gehst solang horizontal weiter, bis du ne null findest und läufst dann von deinen gesipeicherten positionen nach unten...

Latest blogs: Oracle übernimmt Sun, Java SE 6 Update 12 verfügbar, Java 1.6.0 Update 10

JKostiK

Beginner

Posts: 2

Friday, June 29th 2007, 12:37am

Genau BennyBunny! Deine Interpretation meines Problems ist richtig vermutet. Entschuldigt bitte wenn meine Ausgangsbeschreibung nicht deutlich war. Doch inzwischen habe ich eine Lösung...

Java Quellcode

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;
}