uCoder | 1262 | Nível: 5 | Tempo Limite: 3
Bons amigos
Adaptado por Erich Rodrigues
Competição: Interfatecs 2016 1ª Fase
Você já deve conhecer a história de João e Maria não é? Bem, esqueça, ela não é fiel ao que acontece na versão mais moderna da história onde João, Maria e a Bruxa são na verdade melhores amigos. Eles vivem em tanta harmonia com a antiga Bruxa má (atualmente Bruxa boa), que sempre participam de jogos e competem para descobrir quem é o melhor para encontrar os doces que estão escondidos na floresta.
O jogo funciona da seguinte forma, alguém fora do trio esconde os doces em algum lugar da floresta, para então João, Maria e Bruxa começarem a procurar. Para procurarem, a cada passo dado, jogam uma migalha de pão no chão. Quando um dos personagens encontra os doces, são contabilizadas quantas migalhas de pão gastou e, ao final, os valores são comparados e verifica-se quem foi mais eficiente, gastando menos migalhas. É importante ressaltar que na floresta existem muitas árvores o que pode atrapalhar ou mesmo impedir a passagem de algum dos participantes.
Os três personagens começam de um ponto específico (nunca igual ao de um amigo), um de cada vez, ou seja, enquanto um estiver na floresta procurando os doces os outros estarão aguardando em suas posições, sendo que o personagem da vez poderá inclusive passar pelos mesmos locais em que estão seus colegas. Em relação à movimentação, todos só podem andar na vertical e na horizontal, porém, existe uma regra de conduta entre os amigos, cada um deles assume que cumprirá uma ordem para a escolha das direções, sendo que a mais prioritária está mais à esquerda e a menos prioritária está mais à direita. Guie-se pela rosa dos ventos ilustrada na Figura 1
Ou seja, sempre que for possível escolher uma direção para seguir caminho, João (por exemplo) optará em ir ao Norte. Caso esteja bloqueada, a direção escolhida será Leste; se estiver impedido, escolherá Sul; se nenhuma das anteriores for possível, escolherá Oeste.
Uma possível configuração da floresta, com a posição dos personagens, os caminhos livres, as árvores e os doces, está ilustrada na Figura 2.
É válido lembrar alguns pontos:
- Como são amigos, nenhum dos personagens tentará trapacear, portanto não podem sair dos limites da floresta, contornando-a para tentar chegar aos doces;
- Cada personagem pode começar em qualquer lugar da floresta, porém jamais na mesma posição de um colega;
- Todo personagem joga uma migalha em todo ponto que pisar, ou seja, a posição inicial e a posição final (a dos doces, se forem encontrados) também terão migalhas.
Entrada
A entrada contém vários casos de teste. A primeira linha de cada caso de teste contém um inteiro N (0 ≤ N ≤ 100), indicando o número de casos. A segunda linha contém dois valores inteiros A e L (4 ≤ L, C ≤ 100) que indicam a altura e a largura da floresta, vista como representada na Figura 2. As próximas A linhas contêm L caracteres representando a floresta, onde o caractere '#' representa uma árvore, o caractere '.' um espaço livre, o caractere 'J' representa a posição inicial de João, o caractere 'M' a posição inicial de Maria, o caractere 'B' a posição inicial da Bruxa e o caractere 'D' a posição dos doces.
Saída
Para cada caso de teste, deverá ser impresso o nome de quem foi mais eficiente, podendo ser joao (minúsculo e sem acentuação), maria (minúsculo) ou bruxa (minúsculo), um espaço em branco e a quantidade de migalhas gastas pelo personagem vencedor. Caso ocorra um empate entre dois ou mais personagens que conseguiram chegar aos doces, imprima apenas empate (minúsculo). Caso ninguém consiga chegar aos doces, imprima somente ninguem (minúsculo e sem acentuação). Imprima uma quebra de linha após cada caso.
| Exemplo de Entrada | Exemplo de Saída |
|---|---|
|
5 |
maria 9 |