Perdido entre ilhas

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).

O nosso novo método run() consistirá de dois modos: o nosso buggle vai alternar entre o "modo de andar para o norte" e o "modo de seguir à esquerda". Começa no "modo de andar para o norte" e alternar para "seguir à esquerda" quando tiver uma parede ao norte (não se esqueça de garantir que tem uma parede à sua esquerda antes de alternar para o modo "seguir a esquerda"). Alterna para "andar para o norte" assim que o seu buggle estiver a olhar para o norte e não estiver em frente de um muro durante a sua viagem ao redor do muro à esquerda dele. O mais fácil de escrever tal máquina de estado é algo como
[!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 do caso default (matching _), ou scala irá dar um erro já que o seu "matching" vai estar incompleto.[/!]

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?