Trouver le chemin le plus court pour les pions synchronisés dans un labyrinthe

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