se por acaso eu bater em um caminho que já foi percorrido, então isso significa que preciso fazer backtrack e posso abortar essa descida
Vou marcar pontos já visitados naquela descida em específico com um X. Quando for necessário fazer o backtracking, marcarei os pontos do antigo caminho com B. Quando chegar no alvo, marcarei com o sucesso com Y:
Agora, vamos ver o problema sendo solucionado com uma busca em largura. Aqui, vamos evitar fazer qualquer espécie de caminhar por cima do caminho já percorrido (como fizemos na bisca em profundidade). Colocarei no canto inferior esquerdo da animação qual o nível de profundidade que estou expandindo:
Ser fôssemos usar outra busca, a busca A* atenderia e seria ainda melhor do que a busca em largura. Porém ela é uma heurística, não uma busca puramente sistemática.
Um grupo de N pessoas liberou uma horda de zumbis no laboratório do alto das montanhas. Para escapar dessa horda, eles precisam atravessar uma ponte. Porém, tem um problema aqui: só tem uma única pessoa com lanterna e está escuro demais. Então, só é possível atravessar a ponte com uma pessoa segurando a lanterna e outra a seguindo, logo atrás. E tem outra coisa, cada pessoa possui um tempo diferente para atravessar a ponte, e, quando 2 pessoas atravessarem ao mesmo tempo, elas precisam andar no ritmo da pessoa mais lenta.
A entrada será fornecida em duas linhas. Na primeira, temos um número N com a quantidade de pessoas. Na segunda linha, terão N números com o tempo (em minutos) que cada pessoa leva para atravessar a ponte.