- Descreva como você pode encontrar o caminho para sair de um labirinto. Você tem um saco de moedas antigas com você.
Passo 1
O enunciado pede para descrever uma forma sistemática de encontrar a saída de um labirinto usando um saco de moedas antigas. O conteúdo envolvido é busca em grafos e técnicas de backtracking, além de marcação de caminhos para evitar revisitar pontos já explorados.
Passo 2
Comece na entrada do labirinto e ande sempre até encontrar um ponto onde há mais de uma direção possível (uma encruzilhada) ou até chegar a um beco sem saída. Sempre que você chegar a uma encruzilhada, deixe uma moeda no chão para marcar que esse ponto já foi visitado.
Passo 3
Ao escolher um ramo numa encruzilhada, siga por ele até encontrar outra encruzilhada ou beco. Se chegar num beco sem saída, você sabe que esse caminho não leva à saída, então pegue de volta a moeda deixada na última encruzilhada e retorne até ela.
Na encruzilhada, escolha outro ramo que ainda não tenha moeda de marcação e repita o processo. Cada vez que você descarta um caminho sem saída, remova a última moeda colocada, voltando no histórico de decisões—isso é o backtracking.
Na encruzilhada, escolha outro ramo que ainda não tenha moeda de marcação e repita o processo. Cada vez que você descarta um caminho sem saída, remova a última moeda colocada, voltando no histórico de decisões—isso é o backtracking.
Passo 4
Continue explorando ramos alternativos em cada encruzilhada usando as moedas como marcadores de “visitado” até que você alcance a saída do labirinto. Quando encontrar a saída, você terá garantido que todos os caminhos inválidos foram descartados.
Passo 5
Por fim, o número de moedas no chão mostra quantas encruzilhadas você ainda não descartou, mas uma vez fora do labirinto basta recolher todas as moedas para não deixar rastros.
Resposta
Use um algoritmo de backtracking marcado por moedas: em cada encruzilhada deixe uma moeda, explore ramos até becos sem saída, então remova a moeda e volte para testar outro caminho; repita até encontrar a saída.