Minimale Entfernung von Hindernissen, um die Ecke zu erreichen

2290. Minimale Entfernung von Hindernissen, um die Ecke zu erreichen

Schwierigkeit:Schwer

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

Sie erhalten ein 0-indiziertes 2D-Integer-Array-Gitter der Größe m x n. Jede Zelle hat einen von zwei Werten:

• 0 stellt eine leere Zelle dar,
• 1 stellt ein Hindernis dar, das entfernt werden kann.

Sie können von und zu einer leeren Zelle nach oben, unten, links oder rechts wechseln.

Geben Sie die Mindestanzahl der Hindernisse zurück, die Sie entfernen müssen, damit Sie sich von der oberen linken Ecke (0, 0) nach unten rechts bewegen können Ecke (m - 1, n - 1).

Beispiel 1:

• Eingabe: Gitter = [[0,1,1],[1,1,0],[1,1,0]]
• Ausgabe: 2
• Erklärung: Wir können die Hindernisse bei (0, 1) und (0, 2) entfernen, um einen Pfad von (0, 0) nach (2, 2) zu erstellen.
  • Es kann gezeigt werden, dass wir mindestens 2 Hindernisse beseitigen müssen, also geben wir 2 zurück.
  • Beachten Sie, dass es möglicherweise andere Möglichkeiten gibt, zwei Hindernisse zu beseitigen, um einen Pfad zu erstellen.

Beispiel 2:

• Eingabe: Gitter = [[0,1,0,0,0],[0,1,0,1,0],[0,0,0,1,0]]
• Ausgabe: 0
• Erklärung:Wir können von (0, 0) nach (2, 4) wechseln, ohne irgendwelche Hindernisse zu entfernen, also geben wir 0 zurück.

Einschränkungen:

• m == Gitterlänge
• n == grid[i].length
• 1 5
• 2 5
• Grid[i][j] ist entweder 0 oder 1.
• Gitter[0][0] == Gitter[m - 1][n - 1] == 0

Hinweis:

1. Modellieren Sie das Gitter als Diagramm, in dem Zellen Knoten sind und Kanten zwischen benachbarten Zellen liegen. Kanten zu Zellen mit Hindernissen kosten 1 und alle anderen Kanten kosten 0.
2. Könnten Sie die 0-1 Breitensuche oder den Dijkstra-Algorithmus verwenden?

Lösung:

Wir müssen dieses Problem mithilfe eines Diagramms modellieren, in dem jede Zelle im Gitter ein Knoten ist. Das Ziel besteht darin, von der oberen linken Ecke (0, 0) zur unteren rechten Ecke (m-1, n-1) zu navigieren und dabei die Anzahl der Hindernisse (1s) zu minimieren, die wir entfernen müssen.

Ansatz:

1. Grafikdarstellung:

   • Jede Zelle im Raster ist ein Knoten.
   • Bewegungen zwischen benachbarten Zellen (oben, unten, links, rechts) werden als Kante behandelt.
   • Wenn sich eine Kante durch eine Zelle mit einer 1 (Hindernis) bewegt, betragen die Kosten 1 (Hindernis entfernen), und wenn sie sich durch eine 0 (leere Zelle) bewegt, betragen die Kosten 0.

2. Algorithmusauswahl:

   • Da wir die Anzahl der entfernten Hindernisse minimieren müssen, können wir 0-1 BFS (Breadth-First Search mit einer Deque) oder Dijkstras Algorithmus mit einer Prioritätswarteschlange verwenden.
   • 0-1 BFS ist hier geeignet, da jede Kante Kosten von entweder 0 oder 1 hat.

3. 0-1 BFS:

   • Wir verwenden eine Deque (doppelte Warteschlange), um Knoten mit unterschiedlichen Kosten zu verarbeiten:
     • Schiebt Zellen mit Kosten 0 an den Anfang der Doppelschlange.
     • Schieben Sie Zellen mit Kosten 1 an die Rückseite der Doppelschlange.
   • Die Idee besteht darin, das Raster zu erkunden und immer zuerst den Weg zu erweitern, der keine Beseitigung von Hindernissen erfordert, und Hindernisse nur dann zu entfernen, wenn es nötig ist.

Lassen Sie uns diese Lösung in PHP implementieren: 2290. Minimale Entfernung von Hindernissen, um die Ecke zu erreichen

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

// Test Case 1
$grid1 = [
    [0, 1, 1],
    [1, 1, 0],
    [1, 1, 0]
];
echo minimumObstacles($grid1) . PHP_EOL; // Output: 2

// Test Case 2
$grid2 = [
    [0, 1, 0, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 1, 0]
];
echo minimumObstacles($grid2) . PHP_EOL; // Output: 0
?>

Erläuterung:

1. Eingabeanalyse:

   • Das Raster wird als 2D-Array verwendet.
   • Zeilen und Spalten werden zur Grenzprüfung berechnet.

2. Deque-Implementierung:

   • SplDoublyLinkedList wird zur Simulation der Deque verwendet. Es unterstützt das Hinzufügen von Elementen vorne (unshift) oder hinten (push).

3. Besuchtes Array:

   • Verfolgt bereits besuchte Zellen, um redundante Verarbeitung zu vermeiden.

4. 0-1 BFS-Logik:

   • Beginnen Sie bei (0, 0) mit Kosten von 0.
   • Für jede benachbarte Zelle:
     • Wenn es leer ist (grid[nx][ny] == 0), fügen Sie es mit den gleichen Kosten an der Vorderseite der Deque hinzu.
     • Wenn es sich um ein Hindernis handelt (grid[nx][ny] == 1), fügen Sie es mit erhöhten Kosten an der Rückseite der Deque hinzu.

5. Ergebnis zurückgeben:

   • Wenn die untere rechte Ecke erreicht ist, geben Sie die Kosten zurück.
   • Wenn kein gültiger Pfad vorhanden ist (obwohl das Problem einen garantiert), geben Sie -1 zurück.

---

Komplexität:

• Zeitkomplexität: O(m x n), wobei m die Anzahl der Zeilen ist und n ist die Anzahl der Spalten. Jede Zelle wird einmal verarbeitet.
• Raumkomplexität: O(m x n), für das besuchte Array und die besuchte Deque.

Diese Implementierung funktioniert innerhalb der gegebenen Einschränkungen effizient.

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 Entfernung von Hindernissen, um die Ecke zu erreichen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!