Rechteck erkennung innerhalb einer Matix

Status
Nicht offen für weitere Antworten.

masafu

Mitglied
Hallo

ich soll als Übungsaufgabe ein Spielprogrammieren, das Spielfeld besteht aus einer Matrix mit x Zeilen und Y Spalten (soll eingestellt werden können). Ich habe es als ein Zweidimensionales Array dargestellt, in dem besetzt Felder durch einen int größer -1 dargestellt werden.
Mein Problem ist jetzt das ich schon seit Tagen auf der suche nach einem schnellen Algorithmus bin, wie ich innerhalb dieses Array Rechtecke mit mindestens 2x2 besetzten Feldern finde und die größe dieser Rechtecke bestimme.
Kann mir einer von euch bei diesem Problem Helfen?
 
S

SlaterB

Gast
suche suchen suchen?
beginne bei 0,0 und prüfe, ob das Feld besetzt ist und wenn ja, ob auch rechts und unten ebenso,
falls ja dann zum einen nach parallelen dritten + vierten Kanten schauen, also unten nach rechts, rechts nach unten
sowie gleichzeitig von 0,0 aus weiter nach rechts und unten für größere Rechtecke, solange es in einer dieser Richtungen weiter geht,

das ganze für alle i,j in der Matrix
 

masafu

Mitglied
Danke für die schnelle Antwort.

Aber wie gehe ich mit folgendem Beispiel um.
1 für besetzt , 0 für leer

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

hier hat man mehre Möglichkeiten das ganze in Rechtecke aufzuteilen. Gesucht ist als erstes das größte (Anzahl der Felder im Rechteck) dann das nächst größte usw.
In dem Fall 3x3 und dann bleibt noch ein zweites 2x2 übrig.
 
S

SlaterB

Gast
wie gesagt, bei 0,0 anfangen usw.
auf 'wie gehe ich vor' werde ich nicht mehr antworten, mehr kann ich nicht verraten ;)
Programmieren musst du es schon

falls du aber irgendwann
'ich habe nun folgenden Code, bin bei diesem Beispiel an Position x,y suche gerade in Richtung z n Schritte und treffe dabei auf folgende seltsame Situation ..'
fragst, dann könnte ich wieder weiterhelfen



denke am besten erstmal gar nicht über größtes/ kleinstes Rechteck, mehrere Rechtecke in Reihenfolge usw nach
sondern versuche, überhaupt paar Rechtecke zu finden
 
Status
Nicht offen für weitere Antworten.
Ähnliche Java Themen

Ähnliche Java Themen

Neue Themen


Oben