Rechercher des chemins dans une grille Fermé

Question

Bonjour, 

je débute l'algorithmique et j'ai un problème qui se pose:

j'ai une grille L*l avec L comme largeur et l comme hauteur (tous les deux sont des nb entier). Je cherche tous les chemins existants partant de (0,0) et arrivant en (L-1, l-1) en ne me déplaçant uniquement tout droit, à gauche ou à droite, pas en diagonale.

J'ai donc défini l'entête de ma fonction comme suit: 

fonction nombre_chemins(l:entier, L:entier):entier



Je cherche désormais à écrire cette fonction. J'ai lu rapidemment des choses sur dijkstra et astar, peuvent-elles m'être utile ici?

Merci

Char Snipeur · Answer

Salut.
Pas simple comme problème.
Je suppose qu'il y a une condition supplémentaire qui est de ne pas repasser plusieurs fois par une même case, sinon le nombre de solution est infini.
On peut déjà remarqué que pour atteindre ta case finale, il faut avoir L mouvements vers le haut et l vers la droite (en cumulé).  Tu as L*l cases, soit au max l*L mouvements maximum. Un mouvement peut être codé par un couple d'entier (v,h) compris entre -1 et 1 (soit 3 valeurs). Par contre, tout les couples ne sont pas valables, tu peux sortir de la grille ou repasser par un endroit déjà fait. Tu peux aussi faire un cul de sac qui ne mène nulle par.
Pour moi l'algorithme est le suivant, pour chaque case tu as 4 directions différentes. Au moins l'une d'elle est mauvaise (celle d'où tu viens).
Il faut donc contruire un arbre à chaque nouvelle case exploré, ou plutôt le dupliquer. Le plus chiant est alors la gestion des variables.

Rechercher des chemins dans une grille

1 réponse

Discussions similaires