Array/Matrix auswerten...

JKostiK · 27. Juni 2007, 23:08

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 · 28. Juni 2007, 07:26

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ß · 28. Juni 2007, 11:11

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 · 28. Juni 2007, 11:57

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 · 28. Juni 2007, 12:55

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

BennyBunny · 28. Juni 2007, 14:44

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

mad · 28. Juni 2007, 18:24

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 · 28. Juni 2007, 18:30

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...

JKostiK · 29. Juni 2007, 00:37

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

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

Alles anzeigen

http://www.java-forum.org/de/topic51758_array-matrix-auswerten.html
...trotzdem 10xDanke

BennyBunny · 29. Juni 2007, 01:09

uhh, sogar rekursiv

Array/Matrix auswerten...

Array/Matrix auswerten...

Re: Array/Matrix auswerten...

Quellcode

Teilen

Tags