Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

LKING - Sonhos, acredite neles!

Um dos mais importantes ativistas políticos do mundo foi o Dr. Martin Luther King Jr, cujo discurso mais conhecido foi "I have a dream". Em 1964, ele recebeu o Nobel da Paz por seu empenho na luta pelo fim do preconceito racial nos Estados Unidos, e pela sua liderança nos movimentos não violentos. Pouco tempo depois de ter recebido o prêmio, Luther King foi assassinado momentos antes de uma marcha no Memphis.

Além do empenho na luta política, Luther King gostava de jogar quebra-cabeça. Um dos jogos que ele adorava jogar é o seguinte: são dados dois mapas N-por-M, cada um com um robô. Cada mapa contém um ponto inicial e um final. Algumas "casas" do mapa são cercadas por paredes. Uma casa do mapa pode ser ou não um buraco. Um comando dado (Cima, Baixo, Esquerda, Direita) é executado ao mesmo tempo para ambos os mapas. Os robôs não atravessam as paredes e nem flutuam sobre os buracos. O mapa é cercado por buracos. O objetivo é chegar com os dois robôs no ponto final ao mesmo tempo, em até 50 movimentos, se isso for possível.

Neste problema, sua tarefa é dados dois mapas N-por-M, determinar o número mínimo de movimentos que resolve o problema.

Entrada

A primeira linha da instância possui dois inteiros N e M (1 ≤ N, M ≤ 50), indicando o número de linhas dos mapas e o número de colunas dos mapas, respectivamente. Nas linhas seguintes são dados os dois mapas. Para cada mapa teremos N linhas com M caracteres. O caractere "." indica uma posição livre; "#" indica uma posição cercada por paredes; "B" indica um buraco; "R" indica a posição inicial do robô e "F" indica a posição final do robô.

Saída

Para cada instância imprima uma linha contendo o número mínimo de movimentos que resolve o problema, ou impossivel se não for possível resolver o problema com no máximo 50 movimentos.

Exemplo de entrada
2
4 4
....
....
...F
..#R
....
....
.FBB
#..R
4 4
.BFB
...#
.#BB
...R
####
.BBF
....
#R..

Exemplo de saída
3
12


Adicionado por:Wanderley Guimarăes
Data:2008-10-01
Tempo limite:3.269s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP JS-RHINO PERL6 PY_NBC SCALA TCL
Origem:Primeira Seletiva para Maratona de Programacao IME-USP - 2008

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.