17. April 2005
Auf diese prallen jetzt sintflutartige Regengüsse nieder, welche die Hänge hinabrinnen und die abflusslosen Täler allmählich fluten. Irgenwann sind alle diese Täler bis zum Rand gefüllt und sie fangen an, überzulaufen:Jetzt hört es zu regnen auf und es bricht der Winter herein, wodurch alle Talseen blitzartig zufrieren. Es schneit etwas, so dass eine infinitesimal Schneeschicht sich über die Landschaft legt. Nun fliegt ein Satellit über die Gegend und kartographiert die Höhenstufen. Er erkennt jedoch nicht, welche Flächen Gebirge sind und welche Flächen Eisseen.
Gegeben sei ein 2dimensionales Array mit Werten, welches die Höhenstufen des Geländes repräsentiert. Kleine Werte repräsentieren die tiefen Punkte, im Bild schwarz dargestellt, große Werte repräsentieren die Bergspitzen, im Bild weiß dargestellt. Außerhalb des Arrays ist stets der Wert 0 anzunehmen; das ganze ist also quasi eine "Insel im Ozean" (Es gibt keine negativen Werte für die Höhen!). In 3D sähe das dann schick gerendert etwa so aus: Man schreibe nun eine Funktion, welche aus diesem 2D-Array nun die abflusslosen Täler und ihre maximalen Füllstände findet und als Ausgabe ein 2D-Array generiert, welches die Höhenstufen der gleichen Landschaft nach der "Sintflut" repräsentiert.
// already given extern const int Width; extern const int Height; extern const unsigned** heightfield; // todo! void raining(int width, int height, const unsigned** original_landscape, unsigned** filled_landscape);
Ich habe ein kleines Rahmenprogramm geschrieben, welches PGM-Dateien von stdin einliest, raining() aufruft und das Ergebnis nach stdout schreibt. Den Quellcode gibts natürlich auch.// already given extern const unsigned Width; extern const unsigned Height; typedef std::vector< std::vector<unsigned> > Heightfield; extern const Heightfield heightfield; // todo! void raining(int width, int height, const Heightfield& original_landscape, Heightfield& filled_landscape);
// already given static final int Width; static final int Height; static final int[][] heightfield; // todo! void raining(int width, int height, int[][] original_landscape, int[][] filled_landscape);