Frage Gesamtwasserkapazität in einem 2D-Array, das eine topographische Karte darstellt


Diese Frage wurde mir kürzlich in einem Interview gestellt, und ich konnte mir nicht vorstellen, wie ich das umsetzen sollte. Ich hoffe, dass mir jemand zeigen kann, wie ich dieses Problem angehen kann.

Problemstellung: In einem 2D-Array mit ganzen Zahlen wird das gesamte Wasser angezeigt, das gehalten werden kann. Die Zahlen repräsentieren die Höhe in einer Karte (d. H. Die Höhen eines Berges). Das Wasser fließt vom höchsten Berg in ein Tal (höchste bis niedrigste Höhe).

Beispiel 1: Dies ist ein 5 x 3 Matrix. 10 ist der höchste Gipfel. Sie können davon ausgehen, dass das Wasser nach unten fließt und sich an der Kachel 2 sammelt, die sich auf der Koordinate befindet (3, 1). Diese Kachel wird gesammelt 7 Einheiten von Wasser. Bevor zu benachbarten Kacheln von Höhe 9 an Koordinaten verschüttet wird (2, 0) or (3, 0) und in den Ozean fließen (angenommen Kanten sind vom Ozean umgeben). Das gesamte Wasser, das für diese Karte gesammelt wurde, ist also 7.

9  9  9
9 10  9
9  9  9
9  2  10
10 10 10

Beispiel 2:

    9   9  9  9  9 9
    9  10  9  8  2 4
    9   9  9 10  3 5
    9   2  2 10  3 5
   10 10  10 10  9 9

In diesem Fall kann sich das Wasser in den folgenden Koordinaten sammeln:

  1. (3, 1) & (3, 2). Also Gesamtkapazität => 7 + 7 = 14
  2. (1, 4) (2, 4) & (3, 4). Diese Koordinaten können 2, 1 bzw. 1 speichern. Weil das Maximum, das sie halten konnten, 4 ist, bevor Wasser anfängt, an der Koordinate (1, 5) aus der Kante herauszufließen. Also Gesamtkapazität => 2 + 1 + 1 = 4

Über alle Kapazität ist 14 + 4 = 18.

Ich habe versucht, dieses Problem mit Flutfüllung anzugehen. Indem Sie einen Pfad vom höchsten zum niedrigsten Gipfel finden und diesen Pfad verwenden, um das Wasser zu bestimmen, das auf der niedrigsten Höhe gespeichert werden kann. Ich war mir nicht sicher, ob ich auf dem richtigen Weg war. Irgendwelche Gedanken darüber, wie man dieses Problem angeht?


6
2017-08-17 05:28


Ursprung


Antworten:


Du bist auf dem richtigen Weg mit der Flutfüllung. Hier ist ein Ansatz für das Problem.

Markieren Sie zuerst alle Kantenkacheln als fertig.

Erstellen Sie dann eine sortierte Liste der inneren Kacheln, am niedrigsten zuerst.

Führen Sie für jede Kachel in der Liste eine Flutfüllung aus

  1. findet alle Kacheln, die sich auf der gleichen Ebene wie die unterste Kachel befinden (die Tal-Kacheln)
  2. findet die minimale umgebende Fliese (die Outlet Fliese)
  3. bestimmt, ob irgendwelche der Auslassziegel bereits fertig sind

Erhöhen Sie dann das Niveau der Talplättchen, um es an das Niveau des Ausgangsplättchens anzupassen. Wenn das Auslassplättchen fertig ist, sind nun alle Talplättchen fertig. Andernfalls erweitern Sie das Tal, um die Outlet-Kacheln aufzunehmen.


So funktioniert der Algorithmus mit dem zweiten Beispiel der Frage. Anfangs werden Kantenkacheln fertiggestellt und innere Kacheln nicht.

enter image description here

Angenommen, die 2 oben rechts ist die erste. Die Auslassfliese ist die 3. Also erhöhe die 2 auf eine 3 und füge 1 zum gesamten Wasser hinzu. Dann können die 3er auf 4 erhöht werden, was 3 zum Gesamtwasser addiert. Und die 4 ist fertig, so dass das Tal nun fertig ist.

enter image description here

Als nächstes ist eine der 2s in der unteren linken Ecke. Die Flutfüllung wird zwei Talfliesen finden, und die Auslassfliese ist 9. So können wir 7 zu zwei Fliesen addieren, was 14 zum Gesamtwasser addiert. Und einer der Verkaufsstellen ist fertig, so dass das Tal nun fertig ist.

enter image description here

An diesem Punkt ist jede verbleibende Kachel benachbart zu einer Ausgangsfliese, die gleich oder niedriger ist, und ebenfalls fertig. Alle übrigen Steine ​​werden als fertig markiert markiert. Und das gesamte Wasser ist 1 + 3 + 14 = 18.


3
2017-08-17 07:40