Robô Aspirador
Por Flávio Zavan, UFPR 
Brazil
Por Flávio Zavan, UFPR Brazil
Ricciardi, o robô aspirador, recebeu ordens. Deve limpar o máximo possível dos N grãos de sujeira no chão e chegar à estação de recarga. Parece uma tarefa trivial, mas Ricciardi está com a bateria viciada e pode realizar apenas M movimentos antes de esgotá-la.
Localizado em uma sala retangular dividida em W × H células quadradas, o robô pode, em um movimento, se movimentar para a célula adjacente diretamente acima, abaixo, à esquerda ou à direita de sua posição atual, desde que não haja obstáculos nela. Determinado a economizar energia e realizar seu trabalho com maestria, Ricciardi pediu a você para escrever um programa que calcule o número máximo de grãos de sujeira que Ricciardi consegue limpar.
A entrada contém vários casos de teste. A primeira linha de cada caso contém dois inteiros N (1 ≤ N ≤ 8) e M (1 ≤ M ≤ 109). A segunda linha também contém dois inteiros W e H (5 ≤ W, H ≤ 100).
As H linhas seguintes contém W caracteres cada e descrevem a sala. Obstáculos são representados por '#', posições livres por '.' , a posição inicial de Ricciardi por 'R', grãos de sujeira por '*' e a estação de recarga por 'S'.
Ricciardi coleta os grãos automaticamente ao passar por cima deles e consegue andar sobre a estação de recarga como em qualquer posição livre.
A entrada termina com fim-de-arquivo (EOF).
Para cada caso de teste, imprima uma linha com um único inteiro, o número máximo de grãos que Ricciardi consegue coletar chegando à estação de recarga. Se o robô não consegue chegar à estação, imprima -1.
| Exemplo de Entrada | Exemplo de Saída |
|
3 10 |
1 |