Vielen Dank an Simon, der die initiale Idee dieses Problems hervor brachte, an Graeme der feststellte, dass die einfach Version des Problems zu einfach war :) und an Alexandr für die Hilfe beim Korrigieren des Checkers.
Die Sintflut wird in verschiedenen religiösen und epischen Quellen erwähnt. Der Regen war so stark, dass der Wasserspiegel anstieg und sogar die höchsten Gipfel bedeckte. Nachdem der Regen aufgehört hatte und das Wasser verschwunden war, fanden sich die Überlebenden auf dem Gipfel des Berges Ararat (im heutigen Armenien) wieder.
Als Berg mit komplizierter Form aus Tälern und Spalten konnte an einigen tieferen Stellen etwas Wasser zurückbleiben, ähnlich wie bei Seen.
Wir haben eine ebene Karte des Berges als Höhenraster. Angenommen wird, dass jede Gitterzelle eine Achtelmeile lang und breit ist und die Höhen ebenfalls in Achtelmeilen angegeben sind. Die Frage ist, wieviele Kubikachtelmeilen an Wasser zurückgehalten werden.
Eine formale Beschreibung davon, wie das Wasser vom Berg abfließt, ist im Detail schwierig zu erstellen. Es wird daher erwartet, dass man eine gewisse Intuition an den Tag legt, um sich mit den folgenden Grundideen vertraut zu machen:
Eingabe gibt in der ersten Zeile die Größe des Gitters an (eine einzige Zahl, da das Gitter quadratisch ist).
Daraufhin folgt das Gitter selbst, N Zeilen mit N positiven Ganzzahlen.
Ausgabe soll einen einzigen ganzzahligen Wert enthalten - die Wassermenge.
Beispiel:
Eingabe Daten:
6
9 9 9 9 9 9
9 6 5 1 3 9
9 2 9 9 4 9
3 4 9 9 7 9
9 9 9 9 4 9
9 9 9 9 5 9
Antwort:
14
Erklärung: unten dargestellt ist dasselbe Raster wie oben, mit den in Klammern gesetzten höhen der Wasseroberfläche:
9 9 9 9 9 9
9 6 [6][6][6] 9
9 [4] 9 9 [6] 9
3 4 9 9 7 9
9 9 9 9 [5] 9
9 9 9 9 5 9