(Twitter)
Hallo,
ich habe eine Frage die irgendwo zwischen mathematik und Informatik angesiedelt ist:
Sagen wir wir haben ein Spielfeld der Länge 8x8, wobei jedes Spielfeld eine der Farben 0-5 haben kann.
Für uns interessant ist ein Feld nur wenn es eine der Farben 1-5 hat, 0 ist hier ein Sammelwert für Alles Andere.
Sagen wir also wir haben etwas vereinfacht ein Spielfeld wie folgt:
(1,1,2)
(1,1,2)
(3,1,1)
Nun suche ich letztlich nach einem systematischen Vorgehen (was sich in java programmieren lässt)
um alle zusammenhängenden Gruppen an Blöcken, deren Länge, deren Farbe und deren Position zu finden.
im obigen Fall gibt es also eine Gruppe aus Einsen der Länge 6, deren Position bei (x,y)=(1,1) ist
(wir nehmen mal das feld oben links als "Position" einer gruppe)
dann ist da eine gruppe an Zweiern der länge 2, deren Position (1,3) ist.
Und eine theoretische gruppe an Dreien der Länge 1, also ein einzelnes Feld; das juckt uns aber nicht, nur gruppen länge>=2 sind interessant.
Ja, jedenfalls hätte ich gerne einen allgemeinen algorithmus oder prinzipielles vorgehen um systematisch bei einem gegebenenen 8x8 feld entsprechend alle Gruppen mit den erwähnten Eigenschaften Farbe, Länge und Position ausfindig zu machen.
Hat da Jemand eine gute Idee wie man das verallgemeientt lösen kann?
Student, Punkte: 304
public void isSame(Feld a,color c){
if((a schon verbraucht)||(as Farbe ungleich c)){
return;
}
//füge a zur gruppe dazu
isSame(Feld rechts von a)
isSame(Feld unter a)
isSame(Feld links von a)
}
wobei anfangs halt isSame mit dem Startfeld und der Farbe des Startfelds aufgerufen wird.
das Feld oberhalb teste ich daher nicht weil ich eh zeile für zeile die felder durchgehe und daher bei einem startfeld automatisch das feld darüber bereits verbraucht ist per vorgehensweise. ─ densch 04.09.2022 um 21:35
Erst anfangs mal annehmen, jedes einzelne Feld bilde eine eigene Gruppe der Länge 1.
Dann durch diese Gruppe durchgehen und alle Gruppen mit gleicher Farbe dahingehend vergleichen ob sie vielleicht doch eine gemeinsame Gruppe bilden:
Nämlich genau dann wenn sich in der ersten Gruppe und in der 2. Gruppe je ein Stein findet sodass die 2 Steine Nachbarn sind.
Dann sind 2 Steine aus den 2 gruppen benachbart und bilden folglich zusammen eine große Gruppe.
So immer und immer wieder alle Gruppen gleicher Farbe gegeneinander vergleichen bis keine "Fusionen" mehr möglich sind.Dann dürfte die Liste final sein.
Nur sind bei dieser Vorgehensweise sehr viele Vergleiche nötig und es womöglich sehr ineffizient.
Eine andere Idee wäre Folgende:
Man hat (womöglich in einer Matrix gespeichert) hinterlegt weche Felder noch nicht einer Gruzppe zugeordnet wurden.
Nun guckt man sich den ersten Stein bei (1,1) an. der kommt in eine gruppe.
und guckt ob seine nicht-diagonalen Nachbarn auch die selbe farbe haben.
diese bis zu 2 felder kommen auch in die gruppe.
dann guckt man bei denen wiederum ob deren nachbarn die gleiche farbe haben.
Macht man so lange bis man von einem feld der gruppe aus nicht auf was gleichfarbiges in einem schritt stoßen kann, also nichts gleichfarbiges da ist.
damit ist die erste gruppe fertig.
In obiger matrix streicht man natürlich die felder durch, die auf diese weise schon "verbraucht" sind, weil einer gruppe zugeordnet.
nun beginnt man beim nächsten unbenutzten Feld und streckt rekursiv wieder seine fühler aus bis alles gleichfarrbige verbundene gefunden ist.
rinse and repeat bis alle felder verbraucht sind und man eine fertige liste an gruppen hat.
Nur wie man dieses fühler ausstrecken hinkriegt, also von einem startfeld aus in alle richtugnen immer weiter sucht bis man ein "dead end" erreicht, ist mir unklar.
Erinnert mich visuell an tbreiten/tiefensuche, aber wie man sowas umsetzen kann als methode, sit mir unklar.
ich befürchte ja dass es was hässliches mit rekursion wird, da vbin ich dann recht hilflos weil ich rekursion gar nicht gut kann.
Verstehe bis heute die rekursive methode für die türme von hanoi nicht so wirklich,
kriege das geistig nicht ganz gebacken :-/ ─ densch 04.09.2022 um 21:28