Algoritmos y Estructuras de Datos

Intercambiar a los Robots

Estás trabajando en una startup que intenta competir con Boston Dynamics. Uno de los desafíos consiste en lograr que dos robots intercambien sus posiciones en una cuadrícula sin ocupar la misma casilla a la vez.
La cuadrícula tiene altura h y ancho w. El suelo está representado con puntos (.) y las paredes con símbolos de almohadilla (#).
Se permite que los robots se muevan horizontal, vertical y diagonalmente a sus posi­ciones vecinas. Sin embargo, no pueden pasar uno sobre el otro ni atravesar paredes. En cada paso, ambos robots pueden desplazarse (uno o ambos) o también mantenerse donde están. No pueden saltar por encima del otro durante un solo movimiento.
Se te solicita encontrar el número mínimo de pasos necesario para ubicar al primer robot en la posición del segundo, y al segundo robot en la posición del segundo (es decir, para que ambos intercambien lugares).

Entrada

La primera línea de la entrada contiene 2 enteros h y w (1 ≤ h, w ≤ 50).
Las siguientes h líneas contienen w caracteres que representan la cuadrícula.
El primer robot está marcado con la letra A y el segundo robot está marcado con la letra B.

Salida

El programa debe imprimir el número mínimo de pasos requeridos para que los robots intercambien sus posiciones, o Impossible si no se puede lograr.

Ejemplos

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