Array[][] contains Array[][] ?

[JavaBeginner_copy]

Hallo ich hab folgendes Problem. Ich habe ein Array[][] of char, das letztlich wie folgt ausschaut!

________ x-achse
|
y-achse

x x++++++++++++++++++++++++++++++++++++++++++
x x+++++++++++xxxxxxxxxxxxx+++++++++++++++++++++
+++++++++++++++++xxxxxxxx+++++++++++++++++++++
+++++++++++++++++xxxxxxxx+++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++
++++xxxxxxxx++++++++++++++++++++++++++++++++++
++++xxxxxxxx++++++++++++++++++++++++++++++++++
++++xxxxxxxxx+++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++

Also so ein Art Spielfeld .... nun møchte ich aber, dass ich mir eine Funktion berechnet, welches das grøßte Rechteck, dass nur aus "+" besteht, noch verfügbar steht und wo es sich befindet! Um den Restplatz gut auszunutzen brauch ich das ....

Folgenden Algotithmus wollte ich abarbeiten.

• * Fange bei (0,0) an, und prüfe, wie groß man das recheck machen kønnte!
  * Speicher den flächeninhalt (hohe*breite).
  * Finde das naechste Rechteck beginne bei (0,1) ... (0,2) ... (10,0) .... (10,10) ....; wenn der Flächeninhalt groesser als bisher groesster, speicher die rechteck koordinaten (x,y, laenge, hoehe)

Nur wie bekomme ich das hin, dass er mir im Beispiel nicht begonnen bei (0,2) nicht als flaecheninhalt den rest der ersten zeile ausliest, sondern wie hier im beispiel das rechteck so berechnet (fett) -> bei genauem hinschauen sieht man die leichte vervorherbung (Koordinaten des neuen Rechtecks: x=2,y=0,width=11,length=5)

hier schon mal ein versuch meinerseits ...
zuerst berechne ich, die maximale länge, bis ein "x" erscheint und die maximale høhe bis ein "x" erscheint!
(Hier: max laenge bis zum ende, da erste zeile kein "x" enthält; max hoehe bis zum ende, da (2,i) bis zum ende der spalte auch kein "x" enthält ....

ich gehe also in x-richtung, bis zur berechneten max-länge
wenn während pro schritt in x-richtung, in y-richtung ein hindernis kommt, soll die maximale-høhe herabgesetzt werden ...
und wenn die høhe nicht gerade begradigt wurde, soll, wenn in x-richtung ein hindernis kommt, auch die maximale länger herabgesetzt werden ....

also schau ich so zu sagen, so lange, bis ich eine breite und eine hoehe hab, die kein "x" enthält ... nur irgendwie klappt das noch nicht 100%ig ... er bietet mir halt die erste zeile als rechteck an ...

char[][] spielfeld = new char[SpaltenAnzahl][ZeilenLaenge];

 public Rectangle GetMaximalenRestPlatz(int start_x, int start_y) {
        Rectangle tmp = new Rectangle();
        int AktLaenge = 0;
        int AktHoehe = 0;
        int j = start_y;
        int i = 0;
//Berechne maximale länge bis gegenstand kommt
        for (i = start_x; i < this.ZeilenLaenge; i++) {
            if ((spielfeld[j][i]) != "x") {
                AktLaenge++;
            }
        }
        System.out.println("Max Länge: " + AktLaenge);
        i = start_x;
//Berechne maximale høhe bis gegenstand kommt
        for (j = i; j < this.SpaltenAnzahl; j++) {
            if ((spielfeld[i][j]) != "x") {
                AktHoehe++;
            }
        }
//begradigen, da array bei 0,0 anfängt
        AktHoehe--;
        AktLaenge--;
        
     
        int set =0;
        for (i = start_x; i< AktLaenge;i++) //in x-Richtung gehen
        {
            for (j=start_y;j < AktHoehe; j++) //in y-Richtung gehen
            {
                if ((spielfeld[j][i]) == "x") {
                AktHoehe=j-1; //høhe neu einstellen, da gegenstand auf der hoehe gefunden
                set = 1;
                }  
                else set=0;
                    
            }
                if ((set == 0)&&(spielfeld[j][i] == "x")) {
                AktLaenge=i-1; //weiteneu einstellen, da gegenstand auf der weite gefunden
                }               
        }
        
        
        System.out.println("Max Hoehe: " + AktHoehe);
        System.out.println("Raum-Platz: " + AktHoehe * AktLaenge);
        tmp.x = 0;
        tmp.y = 0;
        tmp.width = AktLaenge;
        tmp.height = AktHoehe;
        System.out.println("Rechteck: "+ tmp.toString());
        return tmp;
    }

Wenn das net geht, wollte ich es mit einem art array.contains probieren ...

sprich:

char[][] subarray = new char[2][3];
char[][] spielfeld = new char[SpaltenAnzahl][ZeilenLaenge];
Arrays.fills(subarray,"+"),

Point Pos Arrays.contains(subarray,spielfeld);
Pos.x = x-Koordinate
Pos.y = y-Koordinate

->also gibt es subarray in spielfeld beginnend an der position Pos!
Nur solche Funktionen gibt's na türlich wieder nicht bei Java^^

 

[SlaterB]

da du anscheinend aber das Problem schon gut durchdachst hast,
hier grob vollständig meine Idee (ich weiß nicht genau, ob dein Algorithmus das schon macht):

du beginnst beim Startpunt +
dann schaust du nur die waagerechte Achse an,
bis zu einer maximalen Länge, entweder Ende des Arrays oder ein x
->
++++++++++++++++++++++++++
Startpunkt a, Endpunkt b

wenn diese erste Zeile fertig ist, gehts los Richtung y-Achse,
du schaust dir die nächste Zeile an, von a bis b in dieser Zeile,
wenn alles + ist, dann ist das ok, dann gehts mit der nächsten Zeile weiter,
ansonsten hast du irgendwann

++++++++++++++++++++++++++
+++++++++++++x

zu diesem Zeitpunkt machst du zwei Dinge,
1. die bisherigen Zeilen (können ja mehrere sein) von a bis b bilden ein mögliches größtes Rechteck, das musst du dir merken,
temp hast du ja schon,
wenn tmp bereits vorhanden und größer ist, dann vergessen
2. b setzt du auf die neue kleinere Größe, die Anzahl der Zeilen verändert sich nicht,
neue Ausgangssituation ist dann
+++++++++++++
+++++++++++++

und schon gehts wie zuvor mit der nächsten Zeile weiter, mehr gibts fast nicht zu beachten,
am Ende ist tmp das größte Rechteck

noch Randbedingungen:
1. wenn alle Zeilen durchlaufen sind, das untere Ende des Array erreicht ist,
dann natürlich aufhören und auch noch das aktuelle Rechteck mit tmp vergleichen

2.
in der Situation
+++++++++++++
+++++++++++++
x

also x gleich zu Beginn einer neuen Zeile, kann man praktisch genauso verfahren wie bei Randbedingung 1

---------

falls du meinst, dass du das auch so hast,
dann poste bitte deinen Code nochmal zusammen mit einer lauffähigen main, welche das Array setzt,
muss kein riesiges sein, aber ich will es zumindest nicht selber zusammenstellen
+ Beschreibung, an welche Stelle der Algorithmus versagt

falls du einen anderen Algorithmus hast, dann auch ne main und noch bisschen mehr erklären,
wie genau der abläuft, idealerweise so wie meine Beschreibung
unter Kommentaren wie 'Höhe neu einstellen' kann ich mir wenig vorstellen

 

[JavaBeginner_copy]

Danke für deinen Hinweis!!!
War von der Idee genauso wie meine, nur das ich nicht auch schon in der Funktion selber die Flächen berechnet habe und temporär gespeichert, sondern dachte, dass es ohne den Weg geht, diese abzuspeichern .... und nach den Schleifen eh die grøßte rauskommt ...

Ich werde ihn gleich mal so implementieren und schaun was bei rauskommt!

Immerhin war meine Strategie ja gar nicht so schlecht ..... hatte mir da nur die Zähne ausgebissen, und kam nicht sinnvoll weiter, denn ich wollte nicht für alle x*y-Felder die Ergebnisse in einem Array Of Points oder so speichern!

Dankø

 

[SlaterB]

das ganze stellt natürlich nur die Suche nach dem größten Rechteck von einer bestimmten Start-Position aus dar,
du musst weiterhin das gesamte Array durchlaufen und von jeder möglichen Start-Position aus neu suchen und aus dieser Menge lokal größter Rechtecke am Ende noch das größte heraussuchen,

gut möglich, dass das nicht besonders schnell ist und es weit bessere Algorithmen gibt,
aber man kann ja mit einem einfachen anfangen

 

[JavaBeginner_copy]

Ja, genau das hatte ich ja vor, deshalb wollte ich nicht im Algorithmus selbst, die Speicherung und Verlgleichung vornehmen, denn das ist nun echt etwas bruteforce..... aber bis ich was neues finde, nutze ich das nun so !!!!
Die CPUs werden ja immer schneller .... und was størt mich dann noch der Speicher :bahnhof:

Nee, ist aber eignetlich net mein Stil, so ein Murks zu coden, aber was soll's. Wenns keine bessere Methode gibt, muss ich damit vorlieb nehmen ...

        for (int i=0;i<ZeilenLaenge;i++)
        {
            for (int j=i;j<SpaltenAnzahl;j++)
            {
              ..... GetMaximalenRestPlatz(i, j);  .......
            }
        }