Algoritmo 5: Rota Segura - Descrição e Formato de Entrada/Saída

Algoritmo 5 Rota Segura Expert Tempo máximo de execução 1s DESCRIÇÃO Descrição Com sua ajuda Oto conseguiu escapar do cerco confederado mas isso não significa que as coisas estão tranquilas Ele ainda precisa encontrar uma rota segura de sua posição atual até Poseidônia um planeta coberto por água que fica além da fronteira confederada Nessa rota ele precisa evitar as patrulhas e os postos avançados A rota é dada por uma sequência de setores pelos quais Oto deve passar até chegar em Poseidônia Os setores formam uma espécie de tabuleiro no espaço e sabemos que não podemos ir para setores à direita nem para trás da posição atual por causa do cerco confederado Será que você consegue ajudar Oto a encontrar uma rota segura Formato de entrada A primeira linha da entrada é dada por dois números inteiros N 1 N 20 e M 1 M 20 representando respectivamente o número de setores para a esquerda e para frente onde encontrase Poseidônia em relação à posição atual de Oto lembrese que em relação à representação do tabuleiro na entrada a nave de Oto está virada para baixo e a nave não gira mesmo quando se movimenta A seguir são apresentadas N linhas cada uma contendo M caracteres O primeiro caractere da primeira linha sempre contém a letra O e representa o setor em que Oto se encontra O Mésimo caractere da Nésima linha sempre contém a letra P representando o setor onde Poseidônia se encontra As demais posições são preenchidas com as letras L T e A indicando respectivamente que o setor está livre L possui uma patrulha T ou um posto avançado A As patrulhas só conseguem cobrir o setor em que se encontram mas os postos avançados possuem dispositivos que os permitem vasculhar setores vizinhos acima abaixo a esquerda e a direita Formato de saída A saída deve ser dada por todas as rotas representadas como uma sequência de caracteres que representam movimentos que permitem que Oto chegue a Poseidônia sem ser capturado Os movimentos possíveis são para frente F para trás T para a esquerda E e para a direita D Lembrese que a nave não gira então ela sempre estará virada para a parte de baixo do tabuleiro Caso exista mais de uma rota elas devem ser apresentadas em ordem lexicográfica Caso não exista nenhuma rota possível devese imprimir Sem saida sem acento e sem as aspas Exemplos de Entrada 5 5 OLLTL TLLAL LLLLL LTLLL LTTLP Saída EFFEFEEF EFFEFEFE Entrada 3 3 OLL TLT LTP Saída Sem saida