# Rechteck erkennung innerhalb einer Matix



## masafu (15. Sep 2009)

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?


----------



## SlaterB (15. Sep 2009)

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 (15. Sep 2009)

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.


----------



## SlaterB (15. Sep 2009)

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


----------



## masafu (15. Sep 2009)

edit


----------

