. Puzzle coulissant

773. Puzzle coulissant

Difficulté : Difficile

Sujets : Tableau, recherche en largeur d'abord, matrice

Sur un plateau 2 x 3, il y a cinq tuiles étiquetées de 1 à 5, et un carré vide représenté par 0. Un déplacement consiste à choisir 0 et un nombre adjacent dans 4 directions et à les échanger .

L'état du tableau est résolu si et seulement si le tableau est [[1,2,3],[4,5,0]].

Étant donné le tableau du puzzle, retournez le moins de mouvements requis pour que l'état du tableau soit résolu. S'il est impossible de résoudre l'état du tableau, renvoyez -1.

Exemple 1 :

• Entrée : tableau = [[1,2,3],[4,0,5]]
• Sortie : 1
• Explication : Echangez le 0 et le 5 d'un seul coup.

Exemple 2 :

• Entrée : tableau = [[1,2,3],[5,4,0]]
• Sortie : -1
• Explication : Aucun nombre de mouvements ne permettra de résoudre le tableau.

Exemple 3 :

• Entrée : tableau = [[4,1,2],[5,0,3]]
• Sortie : 5
• Explication : 5 est le plus petit nombre de mouvements qui résout le tableau.
  • Un exemple de chemin :
  • Après le coup 0 : [[4,1,2],[5,0,3]]
  • Après le coup 1 : [[4,1,2],[0,5,3]]
  • Après le coup 2 : [[0,1,2],[4,5,3]]
  • Après le coup 3 : [[1,0,2],[4,5,3]]
  • Après le coup 4 : [[1,2,0],[4,5,3]]
  • Après le coup 5 : [[1,2,3],[4,5,0]]

Contraintes :

• board.length == 2
• planche[i].length == 3
• 0 <= tableau[i][j] <= 5
• Chaque tableau de valeurs[i][j] est unique.

Indice :

1. Effectuez une recherche en largeur, où les nœuds sont les planches de puzzle et les bords si deux planches de puzzle peuvent être transformées l'une en l'autre en un seul mouvement.

Solution :

Nous pouvons appliquer l'algorithme Breadth-First Search (BFS). L'idée est d'explorer toutes les configurations possibles du tableau à partir de l'état initial donné, un mouvement à la fois, jusqu'à atteindre l'état résolu.

Approche:

1. Recherche en largeur d'abord (BFS) :

   • BFS est idéal ici car nous recherchons le chemin le plus court vers l'état résolu.
   • Chaque configuration du plateau peut être considérée comme un nœud, et les bords entre les nœuds représentent des mouvements valides où la tuile 0 est échangée avec une tuile adjacente.
   • Le BFS explorera les configurations du plateau niveau par niveau, garantissant que nous atteignons l'état résolu avec le minimum de mouvements.

2. Représentation de l'État :

   • Nous représenterons le tableau sous forme de chaîne (pour une comparaison et un stockage plus faciles).
   • L'état résolu est "123450" car c'est une représentation linéaire du tableau [[1,2,3],[4,5,0]].

3. Transitions d'État :

   • De chaque état, la tuile 0 peut échanger avec l'une de ses 4 voisines (haut, bas, gauche, droite), si elle se trouve dans les limites du plateau.

4. Suivi des États visités :

   • Nous devons garder une trace des États visités pour éviter les cycles et les calculs redondants.

5. Vérification de l'état résolu :

   • Si à un moment donné la configuration du tableau correspond à l'état résolu, nous renvoyons le nombre de mouvements nécessaires pour y arriver.

6. Gestion des cas impossibles :

   • Si BFS se termine et que nous ne trouvons pas l'état résolu, cela signifie qu'il est impossible de résoudre le puzzle, et nous renvoyons -1.

Implémentons cette solution en PHP : 773. Puzzle coulissant

  
  
  Explication:




Configuration initiale : Nous commençons par convertir la carte 2D en une chaîne 1D pour une manipulation plus facile.

Exécution BFS : Nous mettons en file d'attente l'état initial du tableau ainsi que le nombre de mouvements (en commençant à 0). Dans chaque itération BFS, nous explorons les mouvements possibles (en fonction de la position de la tuile 0), échangeons 0 avec les tuiles adjacentes et mettons les nouveaux états en file d'attente.

États visités : Nous utilisons un dictionnaire pour garder une trace des états du tableau visités afin d'éviter de revisiter et de revenir aux mêmes états.

Validation des bords : Nous vérifions que tout mouvement reste dans les limites de la grille 2x3, en garantissant notamment qu'il n'y a pas de mouvements illégaux qui s'enroulent autour de la grille (comme se déplacer à gauche sur le bord gauche ou à droite sur le bord droit). 

Résultat de retour : Si nous atteignons l'état cible, nous renvoyons le nombre de mouvements. Si BFS se termine et que nous n’atteignons pas l’objectif, nous renvoyons -1.



  
  
  Complexité temporelle :




Complexité BFS : La complexité temporelle de BFS est O(N), où N est le nombre d'états uniques de la carte. Pour ce puzzle, il y en a au maximum 6 ! (720) configurations possibles.



  
  
  Complexité spatiale :



La complexité spatiale est également O(N) en raison du stockage requis pour la file d'attente et les états visités.


Cette solution devrait être suffisamment efficace compte tenu 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!