J'ai donc obtenu cette affectation, dont je ne suis pas sûr de la façon d'aborder. J'ai un tableau 2D dans lequel certaines cellules sont interdites de visite. Ensuite, j'ai besoin de traverser tout le tableau en choisissant l'itinéraire le plus long sans entrer dans les cellules interdites. Je ne peux pas non plus "revenir en arrière" et prendre un autre virage, la traversée devrait toujours aller "en avant". La sortie devrait être le nombre de cellules visitées et dans le bon ordre. L'algorithme devrait être facilement évolutif, au moins pour un tableau avec des cellules 100x100. Voici une photo montrant la tâche.Trouver l'itinéraire le plus long dans le tableau 2D
Comme dans l'image ci-dessus, il n'y a vraiment que deux solutions: Soit suivre le long du bord, puis descendre une cellule, puis à nouveau, tout comme l'exemple. Ou il pourrait juste avoir suivi le long du bord complet. Le nombre de cellules visités doit toujours être le même; 12. J'ai maintenant beaucoup cherché et trouvé de nombreuses variations et à ma connaissance, je devrais être capable d'utiliser peut-être des algorithmes Djikstras, Bellman-Ford, A * ou une sorte de traversée de graphe Depth/Breadth-first. Mais je suis complètement coincé et je ne sais pas où aller à partir d'ici.
Je peux entrer dans toutes les cellules qui ne sont pas rouges. Le but est de traverser autant de cellules que possible, mais je ne devrais pas pouvoir revenir en arrière ou entrer dans le "serpent". Cela ne peut qu'aller de l'avant. Comme dans l'image ci-dessus, il n'y a vraiment que 2 solutions. Soit il suivra tout le bord, soit descendra une cellule comme sur la photo. – GIJOE
Je viens de trouver ceci: http://www.geeksforgeeks.org/longest-possible-route-in-a-matrix-with-hurdles/ Je vais le parcourir :) – GIJOE