Um enunciado que assusta pelo tamanho e pelo nível de detalhes. Neste problema conceitos como uso de pilha, recursividade, manipulação de matrizes, leitura de caracteres e força bruta são exigidos.

Primeiramente, é necessário ler a quantidade de casos de teste propostos (que não era tão grande); depois armazenar o número de linhas e de colunas que serão lidas; o próximo passo é popular uma matriz, algo fácil de cumprir usando apenas dois laços de repetição.

É depois da coleta de dados da entrada que o verdadeiro desafio começa. Note que temos três personagens que devem percorrer a matriz e, de alguma forma, registrar o percurso, afinal queremos saber a quantidade de migalhas gastas. Um modo simples de evitar que áreas já verificadas sejam novamente contabilizadas é demarcando-as, evitando assim que os mesmos caminhos sejam refeitos, culminado em um estouro de pilha, já que cada passo dado será uma chamada recursiva (entendeu o uso de “pilha”?).

Para cumprir o percurso é necessário construir funções que façam chamadas recursivas na ordem em que cada personagem se desloca, ou seja, chamadas que colocam o personagem ao norte, ao sul, ao leste e ao oeste (cima, baixo, direita e esquerda, respectivamente). Também é possível fazer isso com apenas uma função... fica como desafio para os mais destemidos.

Um importante detalhe é que cada personagem fará modificações na matriz durante seu trajeto, logo será útil construir cópias. Após o término do percurso de cada personagem, basta varrer sua matriz-cópia contando quantas migalhas gastou. Lembre-se que é vital saber se cada personagem ao menos conseguiu chegar até os doces.

Por último, é preciso verificar em qual situação o caso de teste se encontra, a dica é seguir essa ordem:
- Ninguém: mesmo com muito esforço os doces não foram encontrados;
- Bruxa: a antiga vilã conseguiu gastar menos migalhas;
- Maria: aparentemente a protagonista feminina foi a mais econômica;
- João: o jovem personagem teve a melhor estratégia e gastou pouco;
- Empate: se nenhum dos casos anteriores é verdade, só resta esse.

Autor: Lucio Nunes de Lira (Fatec São Paulo)