Algoritmi e Strutture Dati

Scambia i robot

Stai lavorando in una startup che cerca di competere con Boston Dynamics. Una delle sfide consiste nel far scambiare posizione a due robot su una griglia senza che si ostacolino a vicenda.
La griglia ha altezza h e larghezza w. Il pavimento è rappresentato da punti (.) e i muri da simboli cancelletto (#).
I robot possono muoversi orizzontalmente, verticalmente e in diagonale verso le posizioni adiacenti. Tuttavia, non possono passare sulla stessa casella o oltrepassare muri. A ogni passo, entrambi i robot possono muoversi o rimanere fermi. Non è consentito che un robot “salti” l’altro durante lo spostamento.
Viene richiesto di determinare il numero minimo di mosse necessario affinché il primo robot occupi la posizione del secondo e il secondo quella del primo.

Input

La prima riga dell’input contiene 2 interi h e w (1 ≤ h, w ≤ 50).
Le successive h righe contengono w caratteri che rappresentano la griglia.
Il primo robot è indicato con la lettera A e il secondo robot è indicato con la lettera B.

Output

Il programma deve stampare il numero minimo di passi necessario per far scambiare posizione ai robot, oppure Impossible se non esiste alcuna soluzione.

Examples

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