begueradj
Messages postés273Date d'inscriptiondimanche 4 octobre 2009StatutMembreDernière intervention24 juin 2014
-
4 déc. 2011 à 23:42
begueradj
Messages postés273Date d'inscriptiondimanche 4 octobre 2009StatutMembreDernière intervention24 juin 2014
-
6 déc. 2011 à 00:49
Bonjour
Je cherche à transformer une matrice qui ne contient que des 0 et des 1 à un arbre. Comment le faire sachant que je ne m'intéresse à ne représenter sous forme d'un arbre que les Matrice[i][j] =0 ?
coucou747
Messages postés12303Date d'inscriptionmardi 10 février 2004StatutMembreDernière intervention30 juillet 201244 5 déc. 2011 à 16:49
ok bon... déjà, tu remplaces si matrice[i][j] par si non matrice[i][j] pour transformer ta matrice en un graph.
Bon sinon, c'est un exemple super simple de parcours de graphs...
voici un dfs, ça ne te renvoie pas le chemin le plus court, mais ça marche sans transformer ta matrice en graph.
int solution(int **m, int n, int d, int e){
if (d == e) return 1;
int i;
for (i = 0; i < n; i++){
if (!m[d][i]){
m[d][i] = 1;
if (solution(m, n, i, e)) return 1;
}
}
return 0;
}
d c'est le noeud de départ
e c'est le noeud d'arrivée
ma fonction renvoie 1 si il y a un chemin, mais stoquer le chemin c'est pas vraiment difficile.
Je t'ai donné le dfs, tu peux chercher toi même comment on fait un bfs, et NON, t'as pas besoin d'une pile, juste d'allouer deux tableaux de taille n.
Bref, le BFS c'est super simple à faire, j'ai vu des jeunes de 14 ans le faire pour le concours prologin...
Fait au moins preuve de courage et commence à faire ton travail tout seul, on t'aidera à débuguer le truc si besoin, mais on ne le fera pas "entièrement" à ta place.
begueradj
Messages postés273Date d'inscriptiondimanche 4 octobre 2009StatutMembreDernière intervention24 juin 20149 5 déc. 2011 à 10:49
Merci de m'avoir répondu.
EN fait, dans ma matrice, je n'ai que des 0 et des 1.
Je prédéfinis ma case de départ et ma case d'arrivée, qui ont comme contenu 0 (je ne m'intéresse qu'aux 0)
Dans cette matrice, je cherche le chemin de la case de départ à la case d'arrivée en enmpruntant que les 0.
On nous a demandé d'implémenter l'algorithme du meilleur d'abord. Or, l'implémenter directement sur la matrice est difficile, donc si je réussis à transformer la matrice à un arbre où les successeurs de la case de départ valant 0 et menant ou pas à la case finale, je pourrais parcourir mon arbre plus facilement.
Vous n’avez pas trouvé la réponse que vous recherchez ?
begueradj
Messages postés273Date d'inscriptiondimanche 4 octobre 2009StatutMembreDernière intervention24 juin 20149 5 déc. 2011 à 16:27
merci pour vos réponses
mais le fait d'arrivé à un élément 0 ne contenant pas de successeurs, je dois remonter en arrière, pour retrouver ma bifurcation et aller dans l'autre côté. Ce retour en arrière, je pense qu'il nécessite une pile, et ça me pose un problème.