Resolvendo Labirintos - Parte 2 Muitas vezes não temos só que encontrar um caminho. Precisamos encontrar o melhor caminho. O melhor caminho aqui é aquele com o menor número de passos caminhados. Para o labirinto dado como exemplo na parte 1, a melhor resposta ainda é aquele mesmo caminho: .X################### .X#.....#.#.#.#.....# #X#####.#.#.#.#.##### #XXXXX#.....#...#...# #####X#.#####.###.#.# #XXXXX#.#.#.#.#...#.# #X#.#.#.#.#.#.#.#.### #X#.#.....#.....#.#.# #X#.###.#.#.#######.# #X#.#...#...#.......# #X#.###.#####.###.### #X#.#...#.#.....#...# #X###.#.#.#####.##### #X#.#.#...#.#.......# #X#.#######.#######.# #X#XXXXX..#.#.....#.# #X#X###X###.###.#.#.# #XXX#..XXXXXXX..#...# #######.#####X####### #.......#....XXXXXXXX ###################.X Onde você precisa dar 52 passos. Para o seu antigo input, a resposta era 72 passos. Para o seu novo input, qual o menor número de passos necessários para sair do labirinto? Materiais de apoio: 1 - CS50AI: DFS - BFS (Em inglês, mas ensina muito bem. Tem boa legenda também) https://www.youtube.com/watch?v=qzhEB8FxxRs 3:10 até 36:23 (ou até o fim caso queiram fazer uma inteligência artificial para jogar o jogo da velha :D) 2 - Site para brincar com algoritmos de exploração: https://clementmihailescu.github.io/Pathfinding-Visualizer/# 3 - Também é possível encontrar materiais em português sobre o assunto procurando no Google por algoritmos de busca por profundidade ou busca em largura. Lá da pra encontrar bons materiais, como os da USP. Esse problema também pode ser resolvido com outros algoritmos, incentivamos também quem quiser buscar por soluções diferentes.