Mindestzeit zum Besuch einer Zelle in einem Raster

2577. Mindestzeit zum Besuch einer Zelle in einem Raster

Schwierigkeit:Schwer

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

Sie erhalten ein m x n-Matrixgitter bestehend aus nichtnegativen ganzen Zahlen, wobei grid[row][col] die minimale Zeit darstellt, die erforderlich ist, um die Zelle (Zeile, col), was bedeutet, dass Sie die Zelle (Zeile, Spalte) nur dann besuchen können, wenn die Besuchszeit größer oder gleich Grid[Zeile][Spalte] ist.

Sie stehen in der oberen linken Zelle der Matrix in der 0^ten Sekunde und müssen zu irgendeiner benachbarten Zelle in der vierten Sekunde wechseln Richtungen: oben, unten, links und rechts. Jede von Ihnen ausgeführte Bewegung dauert 1 Sekunde.

Geben Sie die mindestens Zeit ein, in der Sie die untere rechte Zelle der Matrix besuchen können. Wenn Sie die Zelle unten rechts nicht erreichen können, geben Sie -1.

zurück

Beispiel 1:

• Eingabe: Gitter = [[0,1,3,2],[5,1,2,5],[4,3,8,6]]
• Ausgabe: 7
• Erklärung: Einer der Wege, die wir einschlagen können, ist der folgende:
  • Bei t = 0 sind wir auf der Zelle (0,0).
  • Bei t = 1 gehen wir zur Zelle (0,1). Dies ist möglich, weil Grid[0][1] <= 1.
  • Bei t = 2 gehen wir zur Zelle (1,1). Dies ist möglich, weil Grid[1][1] <= 2.
  • Bei t = 3 gehen wir zur Zelle (1,2). Dies ist möglich, weil Grid[1][2] <= 3.
  • Bei t = 4 gehen wir zur Zelle (1,1). Dies ist möglich, weil Grid[1][1] <= 4.
  • Bei t = 5 gehen wir zur Zelle (1,2). Dies ist möglich, weil Grid[1][2] <= 5.
  • Bei t = 6 gehen wir zur Zelle (1,3). Dies ist möglich, weil Grid[1][3] <= 6.
  • Bei t = 7 gehen wir zur Zelle (2,3). Dies ist möglich, weil Grid[2][3] <= 7.
  • Die letzte Zeit ist 7. Es kann gezeigt werden, dass es sich um die minimal mögliche Zeit handelt.

Beispiel 2:

• Eingabe: Gitter = [[0,2,4],[3,2,1],[1,0,4]]
• Ausgabe: -1
• Erklärung:Es gibt keinen Pfad von der oberen linken zur unteren rechten Zelle.

Einschränkungen:

• m == Gitterlänge
• n == grid[i].length
• 2 <= m, n <= 1000
• 4 <= m * n <= 10>sup>5
• 0 <= Grid[i][j] <= 10>sup>5
• Gitter[0][0] == 0

Hinweis:

1. Versuchen Sie es mit einem Algorithmus, der die kürzesten Pfade in einem Diagramm finden kann.
2. Stellen Sie sich den Fall vor, dass Sie zwischen zwei Zellen der Matrix hin und her wechseln müssen, um einige andere Zellen freizuschalten.

Lösung:

Wir können eine modifizierte Version des Dijkstra-Algorithmus mithilfe einer Prioritätswarteschlange anwenden. Bei diesem Problem müssen wir im Wesentlichen die kürzeste Zeit ermitteln, die erforderlich ist, um von der Zelle oben links aus die Zelle unten rechts zu besuchen, wobei jede Bewegung einer Zeitbeschränkung unterliegt, die auf den Werten im Raster basiert.

Ansatz:

1. Grafikdarstellung: Behandeln Sie jede Zelle im Raster als Knoten. Die Kanten sind die angrenzenden Zellen (oben, unten, links, rechts), zu denen Sie wechseln können.

2. Prioritätswarteschlange (Min-Heap): Verwenden Sie eine Prioritätswarteschlange, um die Zelle immer mit dem geringsten Zeitaufwand zu erkunden. Dadurch wird sichergestellt, dass wir die Zellen in der Reihenfolge verarbeiten, in der wir sie frühestens erreichen können.

3. Geändertes BFS: Für jede Zelle prüfen wir, ob wir zu ihren Nachbarzellen wechseln können, und aktualisieren den Zeitpunkt, zu dem wir sie besuchen können. Wenn eine Zelle zu einem späteren Zeitpunkt als dem aktuellen besucht wird, fügen wir sie mit der neuen Zeit wieder in die Warteschlange ein.

4. Frühes Verlassen: Sobald wir die untere rechte Zelle erreicht haben, können wir die Zeit zurückgeben. Wenn wir die Warteschlange erschöpfen, ohne sie zu erreichen, geben wir -1 zurück.

Lassen Sie uns diese Lösung in PHP implementieren: 2577. Mindestzeit zum Besuch einer Zelle in einem Raster

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

// Example 1
$grid1 = [
    [0, 1, 3, 2],
    [5, 1, 2, 5],
    [4, 3, 8, 6]
];
echo minimumTime($grid1) . PHP_EOL; // Output: 7

// Example 2
$grid2 = [
    [0, 2, 4],
    [3, 2, 1],
    [1, 0, 4]
];
echo minimumTime($grid2) . PHP_EOL; // Output: -1
?>

Erläuterung:

1. Prioritätswarteschlange:
   
   Die SplPriorityQueue wird verwendet, um sicherzustellen, dass die Zellen mit der minimalen Zeit zuerst verarbeitet werden. Die Priorität wird als -time gespeichert, da PHPs SplPriorityQueue standardmäßig ein Max-Heap ist.

2. Durchquerung:
   
   Ausgehend von der Zelle oben links (0, 0) verarbeitet der Algorithmus alle erreichbaren Zellen unter Berücksichtigung des frühesten Zeitpunkts, zu dem jede besucht werden kann (max(0, Grid[newRow][newCol] – (Zeit 1))).

3. Besuchte Zellen:
   
   Ein besuchtes Array verfolgt Zellen, die bereits verarbeitet wurden, um redundante Berechnungen und Endlosschleifen zu vermeiden.

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

5. Zeitberechnung:
   
   Jede Bewegung dauert eine Sekunde, und wenn die Zelle warten muss (d. h. Grid[newRow][newCol] > Zeit 1), wartet der Algorithmus bis zur erforderlichen Zeit.

6. Edge Case:
   
   Wenn die Warteschlange erschöpft ist und die Zelle unten rechts nicht erreicht wird, gibt die Funktion -1 zurück.

---

Komplexitätsanalyse

1. Zeitkomplexität:

   • Jede Zelle wird höchstens einmal zur Prioritätswarteschlange hinzugefügt: O(m x n x log(m x n)), wobei m und n sind die Rastermaße.

2. Weltraumkomplexität:

   • Der Platz für die Prioritätswarteschlange und das besuchte Array beträgt O(m x n).

---

Beispielläufe

Eingang:

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

// Example 1
$grid1 = [
    [0, 1, 3, 2],
    [5, 1, 2, 5],
    [4, 3, 8, 6]
];
echo minimumTime($grid1) . PHP_EOL; // Output: 7

// Example 2
$grid2 = [
    [0, 2, 4],
    [3, 2, 1],
    [1, 0, 4]
];
echo minimumTime($grid2) . PHP_EOL; // Output: -1
?>

Eingang:

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

Diese Lösung ist effizient und funktioniert gut innerhalb der Einschränkungen.

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 vonMindestzeit zum Besuch einer Zelle in einem Raster. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!