Das Management ist begeistert von Ihren Lösungen und tritt mit einem neuen Problem an Sie heran: Es wurde ein potentielles Fördergebiet erkundet und die dortigen unterirdischen Goldvorkommen kartografiert. Wie das Ergebnis einer Kartograerung aussehen könnte, sehen Sie hier: Dort, wo sich unter der Erde Gold bendet, ist auf der Karte ein schwarzes Kästchen zu sehen. Weiße Kästchen kennzeichnen Gebiete, in denen kein Gold zu nden war. Ein Kästchen hat dabei eine Fläche von einem Quadratkilometer. Zusammenhängende Gebiete von schwarzen Kästchen bilden ein Goldvorkommen, wobei wir Kästchen, die sich nur an ihren Ecken berühren, nicht als zusammenhängend zählen. Natürlich ist die tatsächliche Kart des Fördergebietes bedeutend größer. Jedes der Goldvorkommen muss einzeln erschlossen werden, so dass für jedes Vorkommen Erschließungskosten entstehen. Daher lohnt sich die Erschließung eines Vorkommens nur, wenn es eine gewisse Mindestgröße hat (in unserem Fall beträgt sie 5000km2). Sie sollen nun im vorhinein abschätzen, welche Ausgaben und welche Gewinne die Goldgesellschaft erwarten kann.

Ihre Aufgabe: Entwickeln Sie einen Algorithmus, der angeben kann, wieviele Ölvorkommen erschlossen werden sollten und welche Fläche diese insgesamt einnehmen. Verwenden Sie dazu Dynamische Disjunkte Mengen. Implementieren Sie Ihren Algorithmus und testen Sie ihn auf der Instanz goldmine.txt.