Julga que o seu algoritmo é suficiente para escapar de labirintos? Bem, não de todos...
O algoritmo de seguir paredes que usamos até agora só funciona se a entrada e a saída estão próximas de paredes conectadas ao muro externo. Mas se o buggle começa na metade do labirinto, podem existir sessões de paredes desconectadas da parede externa.
É por isto que a estratégia anterior pode deixar o buggle a dar voltas para sempre. Na verdade, o labirinto do qual deve escapar agora contém ilhas e o buggle não começa próximo de um dos muros externos. Experimente se quiser: copie o seu código aqui, aperte o botão executar e veja a sua solução anterior falhar vergonhosamente.
O método de seguir uma parede ainda é bom e permite escapar com muita eficiência de algumas secções do labirinto, por isso não precisamos removê-lo inteiramente. Ao invés disto, queremos parar de seguir a parede sob certas condições. Observe que o baggle fica próximo da borda externa do labirinto. Queremos chegar à borda e então seguir aquela parede. Precisamos, por exemplo, procurar a parede norte antes de segui-la até ao baggle.
Para encontrar a parede do norte, simplesmente ande para o norte enquanto for possível e quando encontrar um obstáculo, deve desviar dele (a usar o método anterior).
[!scala]var state=0; state match { case 0 => // para o norte ... state = 1; case 1 => // seguir a esquerda ... state = 0; case _ => println("Isto não deveria acontecer. Favor me conserte") }[/!][!java|c]int state=0; switch (state) { case 0: // para o norte ... state = 1; break; case 1: // seguir a esquerda ... state = 0; break; }[/!][!python]northRunner = True if northRunner: ... northRunner = False else: # left follower ... northRunner = True[/!][!scala]
Não se esqueça de deixar o buggle apanhar o baggle no final do código.
Tudo pronto. Isto deve ser o suficiente para descobrir como sair deste labirinto e se não for o caso, sempre pode pedir uma dica. Mas não vai precisar, correto?