spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Richtig. Aber eine, die sämtliche Flächen Pixelweise umschließt. Das lässt sich in O ( n*m ) machen.

Ich vermute, dass optimales Ergebnis exponentielle Komplexität hat:
Um die optimale Punktzahl zu erreichen reicht es nicht für jede Vertikale das Optimum zu finden, sondern man muss ja auch die Sache mit den schwach steigenden Linien beachten - das kann auch zu "nicht-intuitiven" Ergebnissen führen, was für das Optimum einen Backtracing-Algorithmus naheliegen lässt. Tjo also muss man x Linien die Score ermitteln: x*Breite*Höhe
Wieviele Möglichkeiten gibt es also für Linien? Nunja also für jede Vertikale hat man soviel Möglichkeiten wie die Vertikalen hoch sind. Für jeden Höhenwert in einer Vertikalen können auch alle anderen anders sein - also Höhe ^ Breite (wie bei einem Zahlenschloss mit Breite Rädern und mit je Höhe Werten)
Alle Möglichkeiten durchgehen wäre also dann O(Breite * Höhe * Höhe ^ Breite) = O(Höhe ^ Breite) also exponentielle Komplexität auf die Breite betrachtet.

Eine Art greedy hab ich übrigens schon ausprobiert - ist eine Katastrophe so wie ich es angegangen bin
Ich hatte für jede Linie an jeden Punkt die lokale Score nur auf die Linie betrachtet ausgerechnet einmal für den Fall, dass Land unten ist und einmal für den Fall dass Wasser unten ist. Je nach Summe der Optimalen Scores dann das bessere von beiden genommen (Optimierungsmöglichkeit: Je nach Gesamtscore entscheiden). Wenn man allerdings ein bischen drüber nachdenkt merkt man schon, dass das bei der Art wie die Punkte errechnet werden nicht gut gehn kann.

Hab mir aber schon was heuristisches überlegt, was ich bei Gelegenheit vielleicht mal ausprobier wenn ich dazu komme... ich muss zugeben, dass ich die Aufgabe erst unterschätzt hab

Edit:
@ BlueCobold
Hmm aber dadurch, dass man die Grenze nur in vertikaler Richtung festlegen kann, kann man ja nicht alle Bereiche eindeutig umschließen. Außerdem wäre das "Glattheitskriterium" ja dann so oder so stark verletzt.

@ drakon
Zu der Header Sache: Mich hat folgendes verwundert: Solange ich die <string> nicht seperat eingebunden habe, hat der Compiler sich bei std::cout << std::string beschwert, nicht aber bei string selbst. Woran kann sowas liegen? Kann es sein, dass durch andere Header eine nicht vollständige Definition dessen, was <string> bietet im Umlauf ist?

Jo, kommt halt drauf an, was man will Optimale Punktzahl oder optimale Ausnutzung. Letztere ist mit O ( n*m ) sicher drin. Ersteres natürlich nicht

n*m stellt wohl die untere Schranke dar -> Omega(n*m).
Begründung: Für eine optimale Lösung muss man sich die Inputdaten anschauen und das sind schon mal n*m viele.

Zitat von »Wümpftlbrümpftl«

@ drakon
Zu der Header Sache: Mich hat folgendes verwundert: Solange ich die <string> nicht seperat eingebunden habe, hat der Compiler sich bei std::cout << std::string beschwert, nicht aber bei string selbst. Woran kann sowas liegen? Kann es sein, dass durch andere Header eine nicht vollständige Definition dessen, was <string> bietet im Umlauf ist?

Das kann gut sein. Wenn du mal nach der Definition von string suchst findest du die in dem Header <xstring> (zumindest bei mir bei VC++2010), welcher wahrscheinlich sonst wo bereits inkludiert wird.
In <string> selbst sind dann Operatoren und zusätzliche Funktionen definiert (unter anderem auch Ein/Ausgabeoperatoren). Es könnte aber genau so gut sein, dass es selbst bei string alleine nicht kompiliert (mit einer anderen Implementierung).

Mal ne Blöde Frag ich hoffe sie steht nicht im Text dann habe ich es überlesen.

Die Grenze wohin gehört die, wenn sie gezogen ist, zum Nord-Teil oder Süd-Teil ?

Oki Danke.