Minimale Kosten für die Erstellung mindestens eines gültigen Pfads in einem Raster

1368. Minimale Kosten für die Erstellung mindestens eines gültigen Pfads in einem Raster

Schwierigkeit:Schwer

Themen: Array, Breitensuche, Diagramm, Heap (Prioritätswarteschlange), Matrix, kürzester Pfad

Gegeben sei ein m x n-Gitter. In jeder Zelle des Rasters befindet sich ein Schild, das auf die nächste Zelle verweist, die Sie besuchen sollten, wenn Sie sich gerade in dieser Zelle befinden. Das Vorzeichen von Grid[i][j] kann sein:

• 1, was bedeutet, dass Sie zur Zelle rechts gehen. (d. h. von Grid[i][j] zu Grid[i][j 1] gehen)
• 2, was bedeutet, gehen Sie zur Zelle links. (d. h. von Grid[i][j] zu Grid[i][j - 1] gehen)
• 3, was bedeutet, in die untere Zelle zu gehen. (d. h. von Grid[i][j] zu Grid[i 1][j] gehen)
• 4, was bedeutet, in die obere Zelle zu gehen. (d. h. von Gitter[i][j] zu Gitter[i - 1][j] gehen)

Beachten Sie, dass es auf den Zellen des Rasters einige Zeichen geben kann, die außerhalb des Rasters zeigen.

Sie beginnen zunächst in der oberen linken Zelle (0, 0). Ein gültiger Pfad im Raster ist ein Pfad, der in der oberen linken Zelle (0, 0) beginnt und in der unteren rechten Zelle (m - 1, n - 1) endet und dabei den Zeichen im Raster folgt. Der gültige Pfad muss nicht der kürzeste sein.

Sie können das Vorzeichen einer Zelle mit Kosten = 1 ändern. Sie können das Vorzeichen einer Zelle nur einmal ändern.

Geben Sie die Mindestkosten zurück, damit das Raster mindestens einen gültigen Pfad hat.

Beispiel 1:

• Eingabe: Gitter = [[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2] ]
• Ausgabe: 3
• Erklärung: Sie beginnen bei Punkt (0, 0). Der Weg zu (3, 3) ist wie folgt. (0, 0) --> (0, 1) --> (0, 2) --> (0, 3)
• Ändern Sie den Pfeil nach unten mit Kosten = 1 --> (1, 3) --> (1, 2) --> (1, 1) --> (1, 0)
• Ändern Sie den Pfeil nach unten mit Kosten = 1 --> (2, 0) --> (2, 1) --> (2, 2) --> (2, 3)
• Ändern Sie den Pfeil nach unten mit Kosten = 1 --> (3, 3) Die Gesamtkosten = 3.

Beispiel 2:

• Eingabe: Gitter = [[1,1,3],[3,2,2],[1,1,4]]
• Ausgabe: 0
• Erklärung:Sie können dem Pfad von (0, 0) bis (2, 2) folgen.

Beispiel 3:

• Eingabe: Gitter = [[1,2],[4,3]]
• Ausgabe: 1

Einschränkungen:

• m == Gitterlänge
• n == grid[i].length
• 1
• 1

Hinweis:

1. Erstellen Sie ein Diagramm, in dem Gitter[i][j] mit allen vier seitlich benachbarten Zellen mit gewichteter Kante verbunden ist. Die Gewichtung beträgt 0, wenn das Vorzeichen auf die angrenzende Zelle zeigt, andernfalls 1.
2. Besuchen Sie mit BFS von (0, 0) zuerst alle Kanten mit Gewicht = 0. die Antwort ist der Abstand zu (m -1, n - 1).

Lösung:

Wir können den 0-1 BFS-Ansatz verwenden. Die Idee besteht darin, das Gitter mithilfe einer Deque (Warteschlange mit zwei Enden) zu durchlaufen, wobei die Kosten für die Änderung der Richtung bestimmen, ob eine Zelle vor oder hinter der Deque hinzugefügt wird. Das Gitter wird als Diagramm behandelt, in dem jede Zelle gewichtete Kanten hat, basierend darauf, ob ihre aktuelle Richtung mit der Bewegung ihrer Nachbarn übereinstimmt.

Lassen Sie uns diese Lösung in PHP implementieren: 1368. Minimale Kosten für die Erstellung mindestens eines gültigen Pfads in einem Raster

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

// Example Test Cases
$Minimale Kosten für die Erstellung mindestens eines gültigen Pfads in einem Raster = [[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2]];
echo minCost($Minimale Kosten für die Erstellung mindestens eines gültigen Pfads in einem Raster) . "\n"; // Output: 3

$Minimale Kosten für die Erstellung mindestens eines gültigen Pfads in einem Raster = [[1,1,3],[3,2,2],[1,1,4]];
echo minCost($Minimale Kosten für die Erstellung mindestens eines gültigen Pfads in einem Raster) . "\n"; // Output: 0

$Minimale Kosten für die Erstellung mindestens eines gültigen Pfads in einem Raster = [[1,2],[4,3]];
echo minCost($Minimale Kosten für die Erstellung mindestens eines gültigen Pfads in einem Raster) . "\n"; // Output: 1
?>

Erläuterung:

1. Richtungszuordnung: Jede Richtung (1 für rechts, 2 für links, 3 für unten, 4 für oben) wird einem Array von Bewegungsdeltas [dx, dy] zugeordnet.

2. 0-1 BFS:

   • Eine Deque wird verwendet, um Zellen mit geringeren Kosten zu priorisieren. Zellen, deren Richtung nicht geändert werden muss, werden vorne eingefügt (unshift), während diejenigen, die eine Änderung erfordern, hinten eingefügt werden (enqueue).
   • Dadurch wird sichergestellt, dass die Zellen in aufsteigender Reihenfolge der Kosten verarbeitet werden.

3. Entfernungsarray: Ein 2D-Array $dist verfolgt die Mindestkosten, um jede Zelle zu erreichen. Es wird mit PHP_INT_MAX für alle Zellen außer der Startzelle (0, 0) initialisiert.

4. Kantengewichte:

   • Wenn das Vorzeichen der aktuellen Zelle mit der beabsichtigten Richtung übereinstimmt, bleiben die Kosten gleich.
   • Andernfalls verursacht die Änderung der Richtung Kosten in Höhe von 1.

5. Abbruch: Die Schleife endet, sobald alle Zellen verarbeitet wurden. Das Ergebnis ist der Wert in $dist[$m - 1][$n - 1], der die Mindestkosten darstellt, um die untere rechte Ecke zu erreichen.

Komplexität:

• Zeitkomplexität: O(m × n), da jede Zelle einmal verarbeitet wird.
• Raumkomplexität: O(m × n), für das Distanzarray und die Deque.

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 vonMinimale Kosten für die Erstellung mindestens eines gültigen Pfads in einem Raster. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!