2577. Temps minimum pour visiter une cellule dans une grille

difficulté: dur

sujets: array, largeur de recherche, graphique, tas (file d'attente de priorité), matrice, chemin le plus court

vous avez une grille de matrice M x n composée de entières non négatives où le grille [row] [col] représente le temps minimum pour pouvoir visiter la cellule (ligne, col), ce qui signifie que vous pouvez visiter la cellule (ligne, col) uniquement lorsque Vous êtes debout dans la cellule

top-left

de la matrice dans la seconde 0 th , et vous devez passer à ^{toute cellule adjacente} dans les quatre directions: up, bas, gauche, et droit. Chaque mouvement que vous faites prend 1 seconde. return

le temps

minimum requis dans lequel vous pouvez visiter la cellule inférieure droite de la matrice. Si vous ne pouvez pas visiter la cellule inférieure droite, retournez -1 .

Exemple 1:

input:
• grid = [[0,1,3,2], [5,1,2,5], [4,3,8,6]]
output:
• 7
Explication:
• L'un des chemins que nous pouvons emprunter est le suivant: à t = 0, nous sommes sur la cellule (0,0).
  • À t = 1, nous passons à la cellule (0,1). C'est possible car Grid [0] [1]
  • À t = 2, nous passons à la cellule (1,1). C'est possible car Grid [1] [1]
  • À t = 3, nous passons à la cellule (1,2). C'est possible parce que Grid [1] [2]
  • À t = 4, nous passons à la cellule (1,1). C'est possible car Grid [1] [1]
  • À t = 5, nous passons à la cellule (1,2). C'est possible parce que Grid [1] [2]
  • À t = 6, nous passons à la cellule (1,3). C'est possible car Grid [1] [3]
  • À t = 7, nous passons à la cellule (2,3). C'est possible parce que Grid [2] [3]
  • Le dernier temps est 7. On peut montrer que c'est le temps minimum possible.

Exemple 2:

entrée:
• grid = [[0,2,4], [3,2,1], [1,0,4]]
output:
• -1
Explication:
• Il n'y a pas de chemin du haut à gauche vers la cellule inférieure droite.

contraintes:

m == grid.length

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

Indice:

essayez d'utiliser un algorithme qui peut trouver les chemins les plus courts d'un graphique.

1. Considérez le cas où vous devez faire des allers-retours entre deux cellules de la matrice pour déverrouiller d'autres cellules.

Solution:

Nous pouvons appliquer une version modifiée de

algorithme de Dijkstra

en utilisant une file d'attente de priorité . Ce problème nous demande essentiellement de trouver le temps le plus court nécessaire pour visiter la cellule inférieure à droite à partir de la cellule supérieure gauche, où chaque mouvement a une contrainte de temps basée sur les valeurs de la grille. Approche:

1. Représentation du graphique

   : Traitez chaque cellule de la grille comme un nœud. Les bords sont les cellules adjacentes (en haut, en bas, à gauche, à droite) que vous pouvez vous déplacer.

2. file d'attente de priorité (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 des premiers temps que nous pouvons les atteindre.

3. bfs modifié

   : Pour chaque cellule, nous vérifierons si nous pouvons nous déplacer vers ses cellules voisines et mettre à jour l'heure à laquelle nous pouvons les visiter. Si une cellule est visitée plus tard que le courant, nous l'ajoutons dans la file d'attente avec le nouveau temps.

4. Exit précoce

   : Une fois que nous atteignons la cellule inférieure droite, nous pouvons retourner le temps. Si nous épuisons la file d'attente sans l'atteindre, retournez -1.

implémentons cette solution dans php:

2577. Temps minimum pour visiter une cellule dans une grille

php / ** * @param entier [] [] $ grille * @return entier * / fonction minimum temps ($ grid) { ... ... ... / ** * Allez sur ./solution.php * / } // Exemple 1 $ grid1 = [ [0, 1, 3, 2], [5, 1, 2, 5], [4, 3, 8, 6] ]] Echo Minimumtime ($ GRID1). Php_eol; // Sortie: 7 // Exemple 2 $ grid2 = [ [0, 2, 4], [3, 2, 1], [1, 0, 4] ]] Echo Minimumtime ($ GRID2). Php_eol; // Sortie: -1 ?>

1. file d'attente de priorité

   : La SPLPriorityqueue est utilisée pour garantir que les cellules avec le temps minimum sont traitées en premier. La priorité est stockée comme -Time car SPLPriorityQueue de PHP est un max-heap par défaut.
   
   

2. Traversal

   : À partir de la cellule supérieure gauche (0, 0), l'algorithme traite toutes les cellules accessibles, compte tenu des premières fois où chacune peut être visitée (max (0, grille [newrow] [newcol] - (temps 1))).
   
   

3. cellules visitées

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

4. Boundary and Validity Check

   : L'algorithme garantit que nous restons dans les limites de la grille et ne traite que les voisins valides.
   
   

5. calcul de temps

   : Chaque mouvement prend une seconde, et si la cellule nécessite d'attendre (c'est-à-dire Grid [newrow] [newcol]> temps 1), l'algorithme attend jusqu'au moment requis.
   
   

6. edge case

   : Si la file d'attente est épuisée et que la cellule inférieure 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
Complexité spatiale
2. :

   L'espace pour la file d'attente prioritaire et le tableau visité est

   o (m x n)
   • .
Exemple de courses

---

Saisir:

$ grid = [ [0, 1, 3, 2], [5, 1, 2, 5], [4, 3, 8, 6] ]] Echo Minimumtime ($ Grid); // Sortie: 7

Saisir:

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

$ grid = [ [0, 2, 4], [3, 2, 1], [1, 0, 4] ]] Echo Minimumtime ($ Grid); // Sortie: -1

Cette solution est efficace et fonctionne bien dans les contraintes.

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

liens de contact

Si vous avez trouvé cette série utile, veuillez envisager de donner le référentiel

une étoile sur GitHub ou de partager le message sur vos réseaux sociaux préférés ?. Votre soutien signifierait beaucoup pour moi!

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

linkedIn

• github