2577. Mindestzeit, um eine Zelle in einem Raster zu besuchen

Schwierigkeit: hard

themen: array, breaddis-first-Suche, Diagramm, Heap (Prioritätswarteschlange), Matrix, kürzester Path

Sie erhalten ein m x n Matrix-Gitter, das aus nicht negativ Zahlen besteht, wobei Grid [row] [col] die minimum Zeit darstellt, die erforderlich ist, um die Zelle zu besuchen (Row, col).

Du stehst in der

top-left Zelle der Matrix in der 0 th ^{Sekunde, und du musst zu} an jedem in den vier Richtungen: Nach unten, links und rechts. Jeder Schritt, den Sie unternehmen, dauert 1 Sekunde.

return

die minimum Zeit erforderlich, in der Sie die untere Rechtezelle der Matrix besuchen können. Wenn Sie die untere rechte Zelle nicht besuchen können, kehren Sie -1 zurück.

Beispiel 1:

• input: grid = [0,1,3,2], [5,1,2,5], [4,3,8,6]]
• output: 7
• Erläuterung: Einer der Pfade, die wir aufnehmen können, ist Folgendes:
  Bei t = 0 sind wir in der Zelle (0,0).
  • .
  Bei t = 1 bewegen wir uns zur Zelle (0,1). Es ist möglich, weil Raster [0] [1]
Bei t = 2 bewegen wir uns in die Zelle (1,1). Es ist möglich, weil Raster [1] [1] Bei T = 3 bewegen wir uns in die Zelle (1,2). Es ist möglich, weil Raster [1] [2] Bei t = 4 bewegen wir uns in die Zelle (1,1). Es ist möglich, weil Raster [1] [1] Bei t = 5 bewegen wir uns in die Zelle (1,2). Es ist möglich, weil Raster [1] [2] Bei t = 6 bewegen wir uns in die Zelle (1,3). Es ist möglich, weil Raster [1] [3] Bei t = 7 bewegen wir uns in die Zelle (2,3). Es ist möglich, weil Raster [2] [3] Das letzte Mal ist 7. Es kann gezeigt werden, dass es die minimale Zeit ist.

Beispiel 2:

• input: grid = [0,2,4], [3,2,1], [1,0,4]]
• output: -1
• Erläuterung: Es gibt keinen Weg von oben links nach unten rechte Zelle.

Einschränkungen:

m == grid.length
n == grid [i] .length
2 4 sup> 5
0 sup> 5
grid [0] [0] == 0

Hinweis:

Versuchen Sie, einen Algorithmus zu verwenden, der die kürzesten Pfade in einem Diagramm finden kann.
Betrachten Sie den Fall, in dem Sie zwischen zwei Zellen der Matrix hin und her gehen müssen, um einige andere Zellen freizuschalten.

Lösung:

Wir können eine modifizierte Version von

dijkstra's algorithm verwenden Priority Queue . Dieses Problem fordert uns im Wesentlichen auf, die kürzeste Zeit zu finden, die erforderlich ist, um die untere rechte Zelle aus der oberen linken Zelle zu besuchen, wo jeder Umzug eine zeitliche Einschränkung auf der Grundlage der Werte im Raster hat.

Ansatz:

1. Graph Repräsentation : Behandle jede Zelle im Raster als Knoten. Die Kanten sind die benachbarten Zellen (nach oben, links, rechts), zu denen Sie übergehen können.

2. Priority Queue (min-heap) : Verwenden Sie eine vorrangige Warteschlange, um die Zelle immer mit der geringsten Zeit zu erforschen. Dies stellt sicher, dass wir die Zellen in der Reihenfolge der frühesten Zeit verarbeiten, die wir erreichen können.

3. modifizierte bfs : Für jede Zelle werden wir überprüfen, ob wir zu seinen benachbarten Zellen wechseln und die Zeit aktualisieren können, zu der wir sie besuchen können. Wenn eine Zelle zu einem späteren Zeitpunkt als in der aktuellen Zeit besucht wird, fügen wir sie mit der neuen Zeit wieder in die Warteschlange hinzu.

4. Early Exit : Sobald wir die untere rechte Zelle erreichen, können wir die Zeit zurückgeben. Wenn wir die Warteschlange erschöpfen, ohne sie zu erreichen, kehren Sie -1 zurück.

Lassen Sie uns diese Lösung in PHP implementieren:

2577. Mindestzeit, um eine Zelle in einem Raster zu besuchen

php /** * @param Integer [] [] $ Grid * @return Integer */ Funktion minimumTime ($ grid) { ... ... ... /** * Gehen Sie zu ./solution.php */ } // Beispiel 1 $ grid1 = [ [0, 1, 3, 2], [5, 1, 2, 5], [4, 3, 8, 6] ]; Echo MinimumTime ($ Grid1). Php_eol; // Ausgabe: 7 // Beispiel 2 $ grid2 = [ [0, 2, 4], [3, 2, 1], [1, 0, 4] ]; Echo MinimumTime ($ Grid2). Php_eol; // Ausgabe: -1 ?>

Erläuterung:

1. priority queue :
   Der SplpriorityQueueue wird verwendet, um sicherzustellen, dass die Zellen mit der Mindestzeit zuerst verarbeitet werden. Die Priorität wird als -Time gespeichert, da der SplpriorityQueue von PHP standardmäßig ein Max -heap ist.
   

2. traversal :
   Ausgehend von der oberen linken Zelle (0, 0) verarbeitet der Algorithmus alle erreichbaren Zellen unter Berücksichtigung der frühesten Zeit, die jeweils jeweils besucht werden kann (max (0, Grid [NewRow] [Newcol] - (Zeit 1))).
   

3. besuchte Zellen :
   Ein besuchter Array verfolgt Zellen, die bereits verarbeitet wurden, um redundante Berechnungen und unendliche Schleifen zu vermeiden.
   

4. Grenz- und Gültigkeitsprüfung :
   Der Algorithmus stellt sicher, dass wir innerhalb der Grenzen des Netzes bleiben und nur gültige Nachbarn verarbeitet.
   

5. Zeitberechnung :
   Jede Bewegung dauert eine Sekunde, und wenn die Zelle warten muss (d. H. Gitter [Newrow] [Newcol]> Zeit 1), wartet der Algorithmus bis zur erforderlichen Zeit.
   

6. edge case :
   Wenn die Warteschlange erschöpft ist und die untere rechte Zelle nicht erreicht ist, gibt die Funktion -1.
   

   .

---

Komplexitätsanalyse

1. Zeitkomplexität :

   Each cell is added to the priority queue at most once:
   • O(m x n x log(m x n)), where m and n are the grid dimensions.

2. space complexity :

   Der Raum für die Prioritätswarteschlange und das besuchte Array ist
   • o (m x n) .

---

Beispiel läuft

Eingang:

$ grid = [ [0, 1, 3, 2], [5, 1, 2, 5], [4, 3, 8, 6] ]; echo minimumtime ($ grid); // Ausgabe: 7

Eingang:

$ grid = [ [0, 2, 4], [3, 2, 1], [1, 0, 4] ]; echo minimumtime ($ grid); // Ausgabe: -1

Diese Lösung ist effizient und funktioniert in den Einschränkungen gut.

wenden Sie sich an links

Wenn Sie diese Serie hilfreich gefunden haben, sollten Sie den

repository einen Stern auf Github geben oder den Beitrag in Ihren Lieblingsnetzwerken teilen? Ihre Unterstützung würde mir viel bedeuten!

Wenn Sie mehr hilfreiche Inhalte wie diesen wünschen, können Sie mir gerne folgen:

• linkedIn
• github