Nombre maximum de mouvements dans une grille

2684. Nombre maximum de mouvements dans une grille

Difficulté :Moyen

Sujets :Array, Programmation dynamique, Matrice

Vous recevez une grille matricielle indexée 0 m x n composée d'entiers positifs.

Vous pouvez commencer à n'importe quelle cellule de la première colonne de la matrice et parcourir la grille de la manière suivante :

• À partir d'une cellule (ligne, col), vous pouvez vous déplacer vers n'importe laquelle des cellules : (ligne - 1, col 1), (ligne, col 1) et (ligne 1, col 1) de telle sorte que la valeur du la cellule vers laquelle vous vous déplacez doit être strictement supérieure à la valeur de la cellule actuelle.

Renvoyer le nombre maximum de mouvements que vous pouvez effectuer.

Exemple 1 :

• Entrée : grille = [[2,4,3,5],[5,4,9,3],[3,4,2,11],[10,9,13,15] ]
• Sortie : 3
• Explication : Nous pouvons commencer par la cellule (0, 0) et effectuer les mouvements suivants :
  • (0, 0) -> (0, 1).
  • (0, 1) -> (1, 2).
  • (1, 2) -> (2, 3). On peut montrer que c'est le nombre maximum de mouvements pouvant être effectués.

Exemple 2 :

• Entrée : grille = [[3,2,4],[2,1,9],[1,1,7]]
• Sortie : 0
• Explication : À partir de n'importe quelle cellule de la première colonne, nous ne pouvons effectuer aucun mouvement.

Contraintes :

• m == grille.longueur
• n == grille[i].longueur
• 2 <= m, n <= 1000
• 4 <= m * n <= 10⁵
• 1 <= grille[i][j] <= 10⁶

Indice :

1. Envisagez d'utiliser la programmation dynamique pour trouver le nombre maximum de mouvements pouvant être effectués à partir de chaque cellule.
2. La réponse finale sera la valeur maximale dans les cellules de la première colonne.

Solution :

Nous pouvons utiliser la Programmation dynamique (DP) pour suivre le nombre maximum de mouvements de chaque cellule, en commençant par n'importe quelle cellule de la première colonne. Voici l’approche étape par étape :

Approche:

1. Définir un tableau DP : Laissez dp[row][col] représenter le nombre maximum de mouvements possibles à partir de la grille[row][col]. Initialisez-le avec 0 pour toutes les cellules.

2. Traverser la grille :

   • Commencez par la dernière colonne et revenez en arrière jusqu'à la première colonne. Pour chaque cellule de la colonne col, calculez les mouvements possibles pour la col-1.
   • Mettre à jour dp[row][col] en fonction des déplacements possibles (ligne - 1, col 1), (ligne, col 1) et (ligne 1, col 1), uniquement si la valeur de la cellule de destination est strictement supérieur à la cellule actuelle.

3. Calculer les mouvements maximum :

   • Après avoir rempli le tableau dp, le résultat sera la valeur maximale dans la première colonne de dp, car elle représente les mouvements maximum à partir de n'importe quelle cellule de la première colonne.

4. Cas Edge :

   • Gérer les cas où aucun déplacement n'est possible (par exemple, lorsque tous les chemins sont bloqués par des valeurs inférieures ou égales dans les cellules voisines).

Implémentons cette solution en PHP : 2684. Nombre maximum de mouvements dans une grille

  
  
  Explication:




Initialisation dp : Nous créons un tableau 2D dp pour stocker le maximum de mouvements de chaque cellule.

Boucle à travers les colonnes : nous parcourons de l'avant-dernière colonne à la première, en mettant à jour dp[row][col] en fonction des déplacements possibles vers les cellules voisines de la colonne suivante.

Calcul des mouvements maximaux : Enfin, la valeur maximale dans la première colonne de dp donne le résultat.



  
  
  Analyse de complexité :




Complexité temporelle : O(m x n) puisque nous traitons chaque cellule une fois.

Complexité spatiale : O(m x n) pour le tableau dp.


Cette solution est efficace compte tenu des contraintes et fonctionnera dans les limites prévues.

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!