Algoritmos e Estruturas de Dados

Trocar os Robôs

Estás a trabalhar numa startup que procura competir com a Boston Dynamics. Um dos desafios envolve dois robôs que precisam de trocar de posição numa grelha, sem nunca se sobreporem.
A grelha possui altura h e largura w, onde o chão está marcado com pontos (.) e as paredes estão marcadas com cerquilhas (#).
Os robôs podem deslocar-se horizontalmente, verticalmente e também na diagonal para as posições vizinhas. No entanto, não lhes é permitido pisarem-se mutuamente nem passarem por cima das paredes. Em cada passo, ambos podem mover-se ou permanecer na posição onde estão. Não é possível saltarem um por cima do outro durante um único movimento.
Deverás determinar qual é o número mínimo de passos necessários para que o primeiro robô vá para a posição do segundo e o segundo vá para a posição do primeiro.

Entrada

A primeira linha de entrada contém 2 inteiros h e w (1 ≤ h, w ≤ 50).
Nas h linhas seguintes, cada linha contém w caracteres que representam a grelha.
O primeiro robô está marcado com a letra A e o segundo robô está marcado com a letra B.

Saída

O programa deve escrever o número mínimo de passos necessários para trocar os robôs de lugar, ou Impossible se a troca não for possível.

Exemplos

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