Chainsaw Massacre Programmieren!
-
Hi,
kennt jemand das Chainsaw Massacre? also das finden der größtmöglichen, zusammenhängenden Fläche in einem Waldstück? Muß ich jetz für die Uni Programmieren, weiß aber nicht so wirklich den Ansatz, außer dass ich das mit einem zweidimensionalen feld machen will. Vielleicht kann mir ja jemand weiterhelfen.Gruß
Arnold
-
Hallo
also zuerst mal ist es wichtig. was für Bäume im Wald stehen. Wenn es Laubbäume sind, mußt du regelmäßig das Systemdatum checken, um nicht unvollständige Speicherbereiche zu bearbeiten, weil die Blätter gelöscht wurden.
Vielleicht erklärst du erstmal etwas mehr von der Aufgabe und deiner Umsetzungsidee?
/Edit : aha, ich war schon verwirrt, was der Film "Texas Chainsaw Massacre" mit Algorithmen zu tun hat.
bis bald
akari
-
Also, eine genaue Beschreibung gibt es hier: www.tcs.uni-luebeck.de/pages/balbach/lehre/akf04/prakt01.pdf
Es soll die breite und länge einer waldstücks eingebeben werden, und die koordinaten von beliebig vielen bäumen auf dieser fläche. und dann soll das programm die größtmögliche fläche ausgeben.
Jetzt wollte ich halt in das array alle koordinaten des feldes, also zeilen und spalten eintrage. weiter bin ich leider noch nicht gekommen
bin schon länger am überlegen wie man am schlausten und am schnellsten diese fläche sucht
-
Also, ich kenne es nicht, würde aber wie folgt dran gehen. Du gehst alle Felder durch. Wenn du ein freies entdeckst klapperst du in alle Richtungen ab, wie groß das zusammenhängende Feld ist und markierst die besuchten Felder, da sie zu keiner anderen zusammenhängenden Fläche gehören können. Wenn du fertig bist weißt du, wo du die Größte zusammenhängende Lichtung ermittelt hast.
Kleines Beispiel:
### # # # #####- Du startest an 1,1 -> belegt.
- 1,2 und 1,3 -> belegt
- 1,4 frei. Aha, von hier aus Größe ermitteln. Wir finden eine Fläche von 3 Einheiten. Position merken...
- Weiter mit 1,5 -> belegt
- 2,1 frei. Ermittelte Größe: 1. Ist also kleiner als das andere Stück.
- 2,2 -> belegt
- 2,3 und 2,4 markiert, also überspringen.
- 2,5 und 3,1 bis 3,5 belegtDas größte Stück ist also um die Position 1,4.
Das wäre mein Vorschlag für eine erste naive Implementierung.
-
Danke schon mal für die Anregung. Da ist nur noch ein kleines Problem, die gesuchte Fläche muß Recheckig sein, zwar kein Quadrat aber rechteckig. Das erschwert das ganze.hmm
-
es geht nur um rechtwinklige freie flächen:
### # # # #####hier gibt es nur 2 mit jeweils 2 feldern: (1,4)+(2,4) bzw. (2,3)+(2,4)
irgendwie kommt mir die aufgabe auch bekannt vor... genau:
http://acm.uva.es/p/v100/10043.html
kannst du ja zum testen deiner lösung benutzen
-
Hm, also wenn die Fläche wirklich nicht Rechteckig sein muß sieht es ja schon ganz anders aus. Hab ich dann wohl aus der Aufgabenstellung falsch verstanden
-
Hmmm, mach doch ein Seedfill auf alle "nichtgefüllten und nicht baumfreien Gebiete" und zähle wieviele Pixel gesetzt wurden.
PS: Hab die Aufgabe nicht gelesen.
-
Laut aufgabenstellung muss die Fläche aber Rechteckig sein, was das Problem erheblich verkompliziert, da dann ein freies Feld zu mehreren, unterschiedlich großen Tanzflächen gehören kann.
-
Einen kleinen Tipp hätte ich für dich. Auf gar keinen Fall würde ich mit einem Feld arbeiten! Das frist verdammt viel Speicherpaltz! Laut Aufgabe kann das Feld die Groesse 10.000x10.000 haben ?! Na dann viel Spaß beim initialisieren, vor allem wenn zB nur 5 Bäume auf dem Feld sind! Die groesse des Feldes ist dir ja bekannt, und du hast auch die Koordinaten der Bäume gegeben, somit hast du alle Informationen, die du brauchst bzw aus deinem geplanten Feld ablesen könntest. Versuche es doch mit einem Vektor von Baumkoordinaten...
-
Diese Aufgaben sind normalerweise so gestellt, dass sie auf aktuellen PCs bequem in den Speicher passen. Und die 13MB entsprechen wohl locker dieser Anforderung. Sogar wenn man's nicht bitweise macht, wären die 100MB noch immer kein Problem.
-
-
***