Algorithmes et Structures de Données

Échanger les Robots

Vous travaillez dans une start-up qui cherche à rivaliser avec Boston Dynamics. L’un des défis consiste à faire en sorte que deux robots intervertissent leurs positions sur une grille sans jamais se superposer.
La grille possède une hauteur h et une largeur w. Le sol est représenté par des points (.) et les murs par des dièses (#).
Les robots peuvent se déplacer horizontalement, verticalement et en diagonale, en avançant d’une cellule adjacente à la fois. Cependant, ils n’ont pas le droit de se marcher dessus ni de traverser les murs. À chaque étape, les deux robots peuvent chacun effectuer un mouvement ou rester à leur place. Ils ne peuvent pas non plus se dépasser l’un l’autre en un seul coup.
Votre objectif est de déterminer le nombre minimum d’étapes nécessaires pour que le premier robot se retrouve à la place du second et que le second se retrouve à la place du premier.

Données en entrée

La première ligne de l’entrée contient 2 entiers h et w (1 ≤ h, w ≤ 50).
Les h lignes suivantes contiennent w caractères qui représentent la grille.
Le premier robot est indiqué par la lettre A et le second robot par la lettre B.

Sortie

Le programme doit afficher le nombre minimum d’étapes nécessaires pour échanger les positions des robots, et indiquer Impossible s’il n’existe pas de solution.

Exemples

Input

4 4
AB.#
###.
...#
.###
Output

11
Input

2 2
AB
..
Output

2
Input

1 3
A.B
Output

Impossible
 

Constraints

Time limit: 15 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue