Trouver le chemin le plus court pour les pions synchronisés dans un labyrinthe
-
05-11-2019 - |
Question
J'ai essayé de peser sur ce problème, et je ne peux tout simplement pas l'obtenir.
Nous avons un $ a Times B $ matrice où chaque cellule correspond à un espace vide, indiqué avec un point ou un mur, indiqué avec $ X $.
Il y a deux pions à différents endroits dans le labyrinthe, leurs mouvements sont synchronisés et ils doivent quitter le labyrinthe (il a plusieurs sorties) dans le même mouvement.
Si l'un se déplace et que l'autre est contre un mur, c'est un mouvement valable et l'autre reste en place.
L'objectif est d'écrire un algorithme qui trouve les mouvements les plus bas possibles pour sortir les deux du labyrinthe en même temps, de complexité temporelle $ mathcal o (a ^ 2 b ^ 2) $.
J'ai reçu des conseils d'utilisation de BFS pour ce problème, mais je ne comprends pas comment cela traiterait tout le retour en arrière à faire. J'ai inclus deux visualisations avec les chemins corrects étiquetés pour aider à expliquer le problème.
Exemple 1: Positions de départ du pion montrées comme des carrés bleus
Exemple 2: Position de départ du pion indiqué comme carré bleu et carré rouge
Pas de solution correcte