Pigé :ccool:
le problème est que tu es effectivement obligé de parcourir le labyrinthe à chaque fois en entier pour trouver les bons numéros.
Il faudrais faire une étude de la complexité.
Avec ma méthode on sait toujours où on est
Version imprimable
Pigé :ccool:
le problème est que tu es effectivement obligé de parcourir le labyrinthe à chaque fois en entier pour trouver les bons numéros.
Il faudrais faire une étude de la complexité.
Avec ma méthode on sait toujours où on est
Il y a un moyen plutot classique en informatique "theorique", c'est de ce ramener à un problème connu. Dans ton cas, comme tu le disais dans ton premier message, c'est de transformer ton labyrinthe en graphe, ou plutot de le voir comme un graphe. Pour ca, il te suffit de considerer chaque case 0 de ta matrice comme d'un sommet. Ensuite, pour les arcs de ton graphe, tu consideres simplement les cases 0 adjacentes. Pour faire simple, tu peux stocker tout ca dans une matrice d'incidence. Ensuite, il te suffit d'appliquer un algorithme connu de recherche du plus court chemin.
Au niveau complexité, ta transformation prend au pire un temps linéaire du nombre de case de ton tableau ( au pire tu construis huit arcs par case, ca reste borné par huit fois la taille de ton labyrinthe, mais tu peux facilement faire des optimisations ) ... Tu re ramène donc à la complexité de l'algo de recherche du plus court chemin que tu choisiras.