Temps minimum pour visiter une cellule dans une grille

2577. Temps minimum pour visiter une cellule dans une grille

Difficulté : Difficile

Sujets : Tableau, recherche en largeur d'abord, graphique, tas (file d'attente prioritaire), matrice, chemin le plus court

Vous recevez une grille matricielle m x n composée d'entiers non négatifs où grille[ligne][col] représente le minimum temps requis pour pouvoir visiter la cellule (ligne, col), ce qui signifie que vous pouvez visiter la cellule (ligne, col) uniquement lorsque l'heure à laquelle vous la visitez est supérieure ou égale à grid[row][col].

Vous vous trouvez dans la cellule en haut à gauche de la matrice à la 0^ème seconde, et vous devez vous déplacer vers n'importe quelle cellule adjacente dans les quatre directions : haut, bas, gauche et droite. Chaque mouvement que vous effectuez prend 1 seconde.

Renvoyer le minimum délai requis pendant lequel vous pouvez visiter la cellule en bas à droite de la matrice. Si vous ne pouvez pas visiter la cellule en bas à droite, renvoyez -1.

Exemple 1 :

• Entrée : grille = [[0,1,3,2],[5,1,2,5],[4,3,8,6]]
• Sortie :7
• Explication : L'un des chemins que nous pouvons emprunter est le suivant :
  • à t = 0, on est sur la cellule (0,0).
  • à t = 1, on passe à la cellule (0,1). C'est possible car grid[0][1] <= 1.
  • à t = 2, on passe à la cellule (1,1). C'est possible car grid[1][1] <= 2.
  • à t = 3, on passe à la cellule (1,2). C'est possible car grille[1][2] <= 3.
  • à t = 4, on passe à la cellule (1,1). C'est possible car grid[1][1] <= 4.
  • à t = 5, on passe à la cellule (1,2). C'est possible car grille[1][2] <= 5.
  • à t = 6, on passe à la cellule (1,3). C'est possible car grille[1][3] <= 6.
  • à t = 7, on passe à la cellule (2,3). C'est possible car grid[2][3] <= 7.
  • Le temps final est 7. On peut montrer que c'est le temps minimum possible.

Exemple 2 :

• Entrée : grille = [[0,2,4],[3,2,1],[1,0,4]]
• Sortie : -1
• Explication : Il n'y a aucun chemin entre la cellule en haut à gauche et la cellule en bas à droite.

Contraintes :

• m == grille.longueur
• n == grille[i].longueur
• 2 <= m, n <= 1000
• 4 <= m * n <= 10>sup>5
• 0 <= grille[i][j] <= 10>sup>5
• grille[0][0] == 0

Indice :

1. Essayez d'utiliser un algorithme capable de trouver les chemins les plus courts sur un graphique.
2. Considérons le cas où il faut faire des allers-retours entre deux cellules de la matrice pour débloquer d'autres cellules.

Solution :

Nous pouvons appliquer une version modifiée de algorithme de Dijkstra en utilisant une file d'attente prioritaire. Ce problème nous demande essentiellement de trouver le temps le plus court nécessaire pour visiter la cellule en bas à droite à partir de la cellule en haut à gauche, où chaque mouvement a une contrainte de temps basée sur les valeurs de la grille.

Approche:

1. Représentation graphique : Traitez chaque cellule de la grille comme un nœud. Les bords sont les cellules adjacentes (haut, bas, gauche, droite) vers lesquelles vous pouvez vous déplacer.

2. File d'attente prioritaire (Min-Heap) : utilisez une file d'attente prioritaire pour toujours explorer la cellule avec le moins de temps requis. Cela garantit que nous traitons les cellules dans l'ordre le plus tôt possible pour les atteindre.

3. BFS modifié : Pour chaque cellule, nous vérifierons si nous pouvons nous déplacer vers ses cellules voisines et mettrons à jour l'heure à laquelle nous pouvons les visiter. Si une cellule est visitée plus tard que l'heure actuelle, nous la remettons dans la file d'attente avec la nouvelle heure.

4. Sortie anticipée : Une fois que nous avons atteint la cellule en bas à droite, nous pouvons retourner l'heure. Si nous épuisons la file d'attente sans l'atteindre, renvoyons -1.

Implémentons cette solution en PHP : 2577. Temps minimum pour visiter une cellule dans une grille

<?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
?>

Explication:

1. File d'attente prioritaire :
   
   SplPriorityQueue est utilisé pour garantir que les cellules avec le temps minimum sont traitées en premier. La priorité est stockée sous la forme -time car SplPriorityQueue de PHP est un tas maximum par défaut.

2. Traversée :
   
   En partant de la cellule en haut à gauche (0, 0), l'algorithme traite toutes les cellules accessibles, en tenant compte de la première heure à laquelle chacune peut être visitée (max(0, grid[newRow][newCol] - (time 1))).

3. Cellules visitées :
   
   Un tableau visité garde la trace des cellules qui ont déjà été traitées pour éviter les calculs redondants et les boucles infinies.

4. Contrôle des limites et de la validité :
   
   L'algorithme garantit que nous restons dans les limites de la grille et ne traite que les voisins valides.

5. Calcul du temps :
   
   Chaque mouvement prend une seconde, et si la cellule nécessite une attente (c'est-à-dire grille[newRow][newCol] > time 1), l'algorithme attend jusqu'au temps requis.

6. Étui Edge :
   
   Si la file d'attente est épuisée et que la cellule en bas à droite n'est pas atteinte, la fonction renvoie -1.

---

Analyse de complexité

1. Complexité temporelle :

   • Chaque cellule est ajoutée à la file d'attente prioritaire au plus une fois : O(m x n x log(m x n)), où m et n sont les dimensions de la grille.

2. Complexité spatiale :

   • L'espace pour la file d'attente prioritaire et le tableau visité est O(m x n).

---

Exemples d'exécutions

Saisir:

<?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
?>

Saisir:

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

Cette solution est efficace et fonctionne bien dans les limites des contraintes.

Liens de contact

Si vous avez trouvé cette série utile, pensez à donner une étoile au référentiel sur GitHub ou à partager la publication sur vos réseaux sociaux préférés ?. Votre soutien signifierait beaucoup pour moi !

Si vous souhaitez du contenu plus utile comme celui-ci, n'hésitez pas à me suivre :

• LinkedIn
• GitHub

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!