Karte des höchsten Gipfels

1765. Karte des höchsten Gipfels

Schwierigkeit:Mittel

Themen:Array, Breitensuche, Matrix

Sie erhalten eine ganzzahlige Matrix isWater der Größe m x n, die eine Karte von Land- und Wasser-Zellen darstellt.

• Wenn isWater[i][j] == 0, ist Zelle (i, j) eine Landzelle.
• Wenn isWater[i][j] == 1, ist Zelle (i, j) eine Wasserzelle.

Sie müssen jeder Zelle eine Höhe zuweisen, die den folgenden Regeln entspricht:

• Die Höhe jeder Zelle darf nicht negativ sein.
• Wenn es sich bei der Zelle um eine Wasserzelle handelt, muss ihre Höhe 0 sein.
• Zwei benachbarte Zellen müssen einen absoluten Höhenunterschied von höchstens 1 aufweisen. Eine Zelle grenzt an eine andere Zelle, wenn die erstere direkt nördlich, östlich, südlich oder westlich der letzteren liegt (d. h. ihre Seiten berühren sich).

Finden Sie eine Höhenzuordnung, sodass die maximale Höhe in der Matrix maximiert ist.

Gib eine ganzzahlige Matrixhöhe der Größe m x n zurück, wobei height[i][j] die Höhe der Zelle (i, j) ist. Wenn es mehrere Lösungen gibt, geben Sie eine beliebige davon zurück.

Beispiel 1:

• Eingabe: isWater = [[0,1],[0,0]]
• Ausgabe: [[1,0],[2,1]]
• Erklärung: Das Bild zeigt die zugewiesenen Höhen jeder Zelle.
  • Die blaue Zelle ist die Wasserzelle und die grünen Zellen sind die Landzellen.

Beispiel 2:

• Eingabe: isWater = [[0,0,1],[1,0,0],[0,0,0]]
• Ausgabe: [[1,1,0],[0,1,1],[1,2,2]]
• Erklärung: Eine Höhe von 2 ist die maximal mögliche Höhe einer Aufgabe.
  • Jede Höhenzuweisung, die eine maximale Höhe von 2 hat und dennoch den Regeln entspricht, wird ebenfalls akzeptiert.

Beispiel 3:

• Eingabe: isWater = [[1,0,0,0,0,0,1,0,0,1,0,0,1,0,0,0,0,0,0,0,0,1,1,0, 0,0,0,0,0,0,1,0,0,1,0,1,1,0,0,1,0 ,1,0,0,0,0,0,0,1,0,0,0,1,1,0,0,0,0,0,1,0,0,0,0,0,0 ,1,0,0,1,0,0,0,0,0,0,0,1,0,0,1,0, 0,0,1,1,0,0,0,1,0,0,1,0,1,1,0,0,0,1,0,1,1,1,0,0,1, 0,0,0,1,1,0,1,0,0,0,1,0,0,1,0,0,0 ,0,1,0,1,0,1,1,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,1,0,0 ,1,0,0,1,0,1,0,1,0,1,1,0,0,0,0,0, 0,0,1,1,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0, 0,0,0,0,0,1,0,1,1,1,0,0,1,0,0,0,0 ,0,1,0,0,0,0,1,0,0,1,0,0],[1,1,0,0,0,0,0,1,0,0,0,1 ,0,0,0,1,1,0,0,1,0,0,1,1,0,1,1,0, 0,1,1,0,0,0,1,0,0,0,0,1,0,0,0,0,0,1,1,0,0,0,1,0,1, 0,0,1,1,0,0,0,1,0,0,0,1,1,0,1,0,1 ,0,0,0,1,0,0,1,1,1,1,0,0,0,0,0,0,1,0,0,0,0,1,0,1,0 ,1,1,0,0,1,0,1,0,0,0,0,1,0,1,0,1, 1,0,0,0,1,1,1,1,0,0,0,1,0,1,0,0,0,0,1,1,1,0,1,0,0, 0,0,0,1,0,1,0,0,1,0,0,0,0,1,0,1,1 ,0,0,0,1,1,1,0,0,0,1,1,0,0,1,0,1,0,0,0,0,1,0,0,0,0 ,0,0,0,0,0,0,0,0,0,0,0,1,0,1,1,0, 1,0,1,1,0,1,0,0,0,0,0,0,0,0,1,0,0,1,0,1,0,0,0,0,0] ,[0,0,1,1,0,0,1,0,0,0,0,1,0,0,0,1 ,0,1,0,1,0,0,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1,0,0,0 ,0,0,0,0,0,1,0,1,0,1,0,0,0,0,1,0, 0,0,1,0,0,0,1,1,0,0,1,0,0,1,0,0,1,0,0,0,0,1,0,1,0, 0,0,0,1,1,1,1,0,0,1,1,0,0,1,0,0,1 ,0,0,0,0,0,1,0,1,0,1,0,1,0,1,1,0,0,0,0,0,0,0,0,1,0 ,0,0,0,0,1,1,1,1,0,0,0,0,0,1,0,0, 1,0,0,0,0,1,1,1,1,0,0,0,0,0,1,0,0,1,0,0,0,0,0,1,1, 0,0,0,1,0,0,0,0,0,1,0,1,1,1,1,1,1 ,0,1,0,0,0,0,1,0,0,1,0,0,0,0,1,1,0,0,1,0,0,0,0,0,1 ,0,1,1,0,0,0,0,1,0,1,0,0],...]
• Ausgabe: [[0,1,2,2,2,1,0,1,1,0,1,1,0,1,2,1,1,2,2,1,1,0,0,1, 2,1,1,2,2,1,0 ,1,1,0,1,0,0,1,1,0,1,0,1,2,2,1,1,1,0,1,1,1,0,0,1,1 ,1,2,1,0,1,2, 3,2,1,1,0,1,1,0,1,2,2,1,2,2,1,0,1,1,0,1,2,1,0,0,1, 2,1,0,1,1,0,1 ,0,0,1,2,1,0,1,0,0,0,1,1,0,1,1,1,0,0,1,0,1,1,1,0,1 ,1,0,1,1,2,1, 0,1,0,1,0,0,1,2,1,2,3,3,2,2,1,0,0,0,1,1,1,0,1,1,0, 1,1,0,1,0,1,0 ,1,0,0,1,2,1,1,2,2,1,0,0,0,1,0,1,1,2,3,2,2,2,2,2,2 ,3,2,3,3,2,1, 0,1,2,1,1,2,1,0,1,0,0,0,1,1,0,1,2,3,2,1,0,1,2,1,1, 0,1,1,0,1,2], [0,0,1,1,2,2,1,0,1,1,1,0,1,2,1,0,0,1,1,0,1,1,0,0,1 ,0,0,1,1,0,0, 1,1,1,0,1,1,1,1,0,1,1,2,2,1,0,0,1,1,1,0,1,0,1,1,0, 0,1,2,1,0,1,2 ,1,0,0,1,0,1,0,1,2,1,0,1,1,0,0,0,0,1,2,3,2,1,1,0,1 ,1,1,1,0,1,0, 1,0,0,1,1,0,1,0,1,1,1,1,0,1,0,1,0,0,1,1,1,0,0,0,0, 1,1,1,0,1,0,1 ,2,1,1,0,0,0,1,0,1,2,2,1,1,0,1,0,1,1,0,1,1,1,1,0,1 ,0,0,1,1,1,0, 0,0,1,2,1,0,0,1,1,0,1,0,1,2,1,1,0,1,2,1,1,1,1,1,1, 2,1,2,3,3,2,1 ,0,1,0,0,1,0,1,0,0,1,0,1,2,1,2,3,2,1,1,0,1,1,0,1,0 ,1,2,1,2,3],[ 1,1,0,0,1,1,0,1,1,2,1,0,1,1,1,0,1,0,1,0,1,1,0,1,2, 1,1,0,1,1,1,1 ,0,1,1,2,1,0,1,1,2,1,2,2,1,1,0,1,0,1,0,1,1,2,1,0,1 ,2,1,...]]

Einschränkungen:

• m == isWater.length
• n == isWater[i].length
• 1
• isWater[i][j] ist 0 oder 1.
• Es gibt mindestens eine Wasserzelle.

Hinweis:

1. Setzen Sie jede Wasserzelle auf 0. Die Höhe jeder Zelle wird durch die nächstgelegene Wasserzelle begrenzt.
2. Führen Sie ein Multi-Source-BFS mit allen Wasserzellen als Quellen durch.

Hinweis: Diese Frage ist dieselbe wie 542. 01 Matrix

Lösung:

Wir können einen Ansatz der Breitensuche (BFS) verwenden. So können wir es Schritt für Schritt angehen:

Problemaufschlüsselung:

1. Wasserzellen: Die Zellen mit 1 stellen Wasserzellen dar und ihre Höhe ist immer 0.
2. Landzellen: Die Zellen mit 0 stellen Landzellen dar, und ihre Höhe sollte so zugewiesen werden, dass benachbarte Landzellen einen Höhenunterschied von höchstens 1 haben.

Ansatz:

1. BFS-Initialisierung:

   • Wir markieren zunächst alle Wasserzellen (Zellen mit dem Wert 1) als Startpunkte im BFS und weisen deren Höhe 0 zu.
   • Dann verarbeiten wir die benachbarten Landzellen (Zellen mit dem Wert 0), um Höhen zuzuweisen.

2. BFS-Traversal:

   • Von jeder Wasserzelle aus dehnen wir uns nach außen aus und erhöhen die Höhe für jede angrenzende Landzelle um 1. Dabei stellen wir sicher, dass der Höhenunterschied zwischen benachbarten Zellen niemals 1 überschreitet.
   • Wir setzen diesen Vorgang fort, bis alle Zellen besucht sind.

3. Ergebnis: Das Ergebnis ist eine Höhenmatrix, die den vorgegebenen Regeln entspricht, wobei die Höhenwerte maximiert sind.

Lassen Sie uns diese Lösung in PHP implementieren: 1765. Karte des höchsten Gipfels

<?php /**
 * @param Integer[][] $isWater
 * @return Integer[][]
 */
function highestPeak($isWater) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$$isWater1 = [[0,1],[0,0]];
$$isWater2 = [[0,0,1],[1,0,0],[0,0,0]];
$$isWater3 = [[1,0,0,0,0,0,1,0,0,1,0,0,1,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,1,0,0,1,0,1,1,0,0,1,0,1,0,0,0,0,0,0,1,0,0,0,1,1,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,1,0,0,0,0,0,0,0,1,0,0,1,0,0,0,1,1,0,0,0,1,0,0,1,0,1,1,0,0,0,1,0,1,1,1,0,0,1,0,0,0,1,1,0,1,0,0,0,1,0,0,1,0,0,0,0,1,0,1,0,1,1,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,1,0,0,1,0,0,1,0,1,0,1,0,1,1,0,0,0,0,0,0,0,1,1,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,1,1,1,0,0,1,0,0,0,0,0,1,0,0,0,0,1,0,0,1,0,0],[1,1,0,0,0,0,0,1,0,0,0,1,0,0,0,1,1,0,0,1,0,0,1,1,0,1,1,0,0,1,1,0,0,0,1,0,0,0,0,1,0,0,0,0,0,1,1,0,0,0,1,0,1,0,0,1,1,0,0,0,1,0,0,0,1,1,0,1,0,1,0,0,0,1,0,0,1,1,1,1,0,0,0,0,0,0,1,0,0,0,0,1,0,1,0,1,1,0,0,1,0,1,0,0,0,0,1,0,1,0,1,1,0,0,0,1,1,1,1,0,0,0,1,0,1,0,0,0,0,1,1,1,0,1,0,0,0,0,0,1,0,1,0,0,1,0,0,0,0,1,0,1,1,0,0,0,1,1,1,0,0,0,1,1,0,0,1,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,1,0,1,0,1,1,0,1,0,0,0,0,0,0,0,0,1,0,0,1,0,1,0,0,0,0,0],[0,0,1,1,0,0,1,0,0,0,0,1,0,0,0,1,0,1,0,1,0,0,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,1,0,1,0,0,0,0,1,0,0,0,1,0,0,0,1,1,0,0,1,0,0,1,0,0,1,0,0,0,0,1,0,1,0,0,0,0,1,1,1,1,0,0,1,1,0,0,1,0,0,1,0,0,0,0,0,1,0,1,0,1,0,1,0,1,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,1,1,1,0,0,0,0,0,1,0,0,1,0,0,0,0,1,1,1,1,0,0,0,0,0,1,0,0,1,0,0,0,0,0,1,1,0,0,0,1,0,0,0,0,0,1,0,1,1,1,1,1,1,0,1,0,0,0,0,1,0,0,1,0,0,0,0,1,1,0,0,1,0,0,0,0,0,1,0,1,1,0,0,0,0,1,0,1,0,0],...];

echo highestPeak($$isWater1) . "\n"; // Output: [[1,0],[2,1]]
echo highestPeak($$isWater2) . "\n"; // Output: [[1,1,0],[0,1,1],[1,2,2]]
echo highestPeak($$isWater3) . "\n"; // Output: [[0,1,2,2,2,1,0,1,1,0,1,1,0,1,2,1,1,2,2,1,1,0,0,1,2,1,1,2,2,1,0,1,1,0,1,0,0,1,1,0,1,0,1,2,2,1,1,1,0,1,1,1,0,0,1,1,1,2,1,0,1,2,3,2,1,1,0,1,1,0,1,2,2,1,2,2,1,0,1,1,0,1,2,1,0,0,1,2,1,0,1,1,0,1,0,0,1,2,1,0,1,0,0,0,1,1,0,1,1,1,0,0,1,0,1,1,1,0,1,1,0,1,1,2,1,0,1,0,1,0,0,1,2,1,2,3,3,2,2,1,0,0,0,1,1,1,0,1,1,0,1,1,0,1,0,1,0,1,0,0,1,2,1,1,2,2,1,0,0,0,1,0,1,1,2,3,2,2,2,2,2,2,3,2,3,3,2,1,0,1,2,1,1,2,1,0,1,0,0,0,1,1,0,1,2,3,2,1,0,1,2,1,1,0,1,1,0,1,2],[0,0,1,1,2,2,1,0,1,1,1,0,1,2,1,0,0,1,1,0,1,1,0,0,1,0,0,1,1,0,0,1,1,1,0,1,1,1,1,0,1,1,2,2,1,0,0,1,1,1,0,1,0,1,1,0,0,1,2,1,0,1,2,1,0,0,1,0,1,0,1,2,1,0,1,1,0,0,0,0,1,2,3,2,1,1,0,1,1,1,1,0,1,0,1,0,0,1,1,0,1,0,1,1,1,1,0,1,0,1,0,0,1,1,1,0,0,0,0,1,1,1,0,1,0,1,2,1,1,0,0,0,1,0,1,2,2,1,1,0,1,0,1,1,0,1,1,1,1,0,1,0,0,1,1,1,0,0,0,1,2,1,0,0,1,1,0,1,0,1,2,1,1,0,1,2,1,1,1,1,1,1,2,1,2,3,3,2,1,0,1,0,0,1,0,1,0,0,1,0,1,2,1,2,3,2,1,1,0,1,1,0,1,0,1,2,1,2,3],[1,1,0,0,1,1,0,1,1,2,1,0,1,1,1,0,1,0,1,0,1,1,0,1,2,1,1,0,1,1,1,1,0,1,1,2,1,0,1,1,2,1,2,2,1,1,0,1,0,1,0,1,1,2,1,0,1,2,1,...]]
?>

Erläuterung:

1. Initialisierung:

   • Wir initialisieren die Höhenmatrix mit -1 für alle Zellen. Die Wasserzellen werden sofort auf 0 gesetzt.
   • Die Wasserzellen werden in die BFS-Warteschlange eingereiht.

2. BFS:

   • Wir verarbeiten die Warteschlange, indem wir jede Zelle aus der Warteschlange entfernen und für jede ihrer Nachbarzellen prüfen, ob sie innerhalb der Grenzen liegt und nicht besucht wird.
   • Wenn es sich um eine gültige (nicht besuchte) Landzelle handelt, weisen wir ihr eine Höhe zu, die um eins höher ist als die Höhe der aktuellen Zelle, und stellen sie zur weiteren Verarbeitung in die Warteschlange.

3. Ergebnis:

   • Nachdem BFS abgeschlossen ist, enthält die Höhenmatrix die höchstmöglichen Höhen für jede Zelle unter Berücksichtigung der gegebenen Einschränkungen.

Zeitkomplexität:

• O(m * n) wobei m die Anzahl der Zeilen und n die Anzahl der Spalten ist. Dies liegt daran, dass jede Zelle während des BFS-Durchlaufs höchstens einmal verarbeitet wird.

Diese Lösung stellt sicher, dass die Matrix mit den richtigen Höhen gefüllt wird, und das BFS garantiert die maximale Höhe für jede Zelle, während die Höhenunterschiedsbeschränkung zwischen benachbarten Zellen beibehalten wird.

Kontaktlinks

Wenn Sie diese Serie hilfreich fanden, denken Sie bitte darüber nach, dem Repository einen Stern auf GitHub zu geben oder den Beitrag in Ihren bevorzugten sozialen Netzwerken zu teilen? Ihre Unterstützung würde mir sehr viel bedeuten!

Wenn Sie weitere hilfreiche Inhalte wie diesen wünschen, folgen Sie mir gerne:

• LinkedIn
• GitHub

Das obige ist der detaillierte Inhalt vonKarte des höchsten Gipfels. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!