Matrices et Arbres

Bonjour à tous,

Alors voila, j'ai un projet à réaliser (en C) et je coince sévèrement.. Je vous explique :
J'ai une matrice motif et une matrice connexion.
La matrice motif et codée en dure dans le code en 8x8 avec ce genre de motif :

xxxxxxxx
x11111xx
x1xxxx1x
x11111xx
x1xxxx1x
x1xxxx1x
x11111xx
xxxxxxxx

La matrice de connexion peut avoir plusieurs forment car nous demandons au préalable à l'utilisateur ou il veut placer la première connexion.
Celle-ci n'est donc qu'un exemple :

123
8X4
765

Alors voici le sujet : nous devons utiliser la matrice de connexion afin de constituer un arbre grâce à la matrice de motif en sachant avec quelle connexion les points sont reliés.

J'ai donc essayé une méthode avec laquelle dès qu'il détecte un 1, il appelle une fonction qui regarde si un des points autour est égal a 1 et se place sur le premier trouvé pour recommencer.
Mais le problème de cette solution c'est que suivant où est la première connexion, tous les points ne sont pas marqués.. (ça marche seulement quand la connexion 1 se trouve au Nord)

Ensuite, j'avais pensé transformer la matrice en graphe, puis trouvé le chemin hamiltonien de celui-ci (mais cela est resté une idée car je n'ai aucune idée de comment modéliser la matrice de motif en graphe..)

Je suis donc à court d'idées.. si quelqu'un pouvais m'aider ce serai sympa

Merci d'avance.

Bonjour

Désolé, c'est encore trop flou. Dans ta matrice "motif" tu ne dis pas ce que représente le "X" et ce que représente le "1". Et dans ta matrice "connexion" (qui n'a pas la même taille donc on ne sait pas comment l'intégrer dans la première) tu ne dis pas ce que représente le "X" et les chiffres.

Salut !

Le x et le 1 sont juste des caractères qui s'affichent en fonction d'une valeur dans la matrice ( 0 ou 1 ) si c'est 1 il affiche 1 si c'est 0 il affiche x .

En gros une Matrice motif [8] [8] qui contient des 0 ou des 1 .

Et une Matrice connexion [3] [3] qui contient une suite de chiffres de 1 à 8 et le X du centre c'est arbitraire, tu peux mettre 0 à la place.

Je suis aussi sur ce sujet, et j'ai essayer 15 000 parcours différents rien à faire je trouve pas de solution non plus :arf:

Et c'est quoi la logique/règle qui lie la matrice "motif" et la matrice "connexion" ???

Alors en fait on doit positionner le centre de la matrice de connexion sur un 1 dans la matrice motif et on doit vérifier toutes les cases au tour, si il y a un 1 on doit dire si c'est une connexion cx.

Par exemple

xxxxxxxx
x11111xx
x1xxxx1x
x11111xx
x1xxxx1x
x1xxxx1x
x11111xx
xxxxxxxx

123
8X4
765

Si l'on positionne le centre de la matrice connexion sur le premier 1 ( donc celui en Motif[1][1]) eh bien on doit dire qu'il y a une connexion :

4 et une connexion 6 .

Ok - Et ensuite ? Suffit d'écrire l'algorithme qui, à partir d'une position précise de la matrice "motif", balaye les 8 directions et qui stocke le chiffre de la matrice "connexion" situé au dessus des autres "1". Une fois cet algorithme bien finalisé, tu l'appliques à tous les "1" de ta matrice "motif". Pourquoi Petrucheqa a parlé de 150000 parcours sans solution ???

C'est justement ce parcours qui me pose problème, non quand je dis 15k parcours différents c'est que j'ai pris un papier un crayon j'ai essayé différents parcours, mais aucun ne donne le résultat souhaité :scarymov: .

Je vois bien ce que ça doit faire mais j'arrive pas a le programmer, c'est ça le soucis ( le fait que les deux tableaux soient pas de la même taille me gène)

Citation:

---

Envoyé par Petrucheqa

j'ai essayé différents parcours, mais aucun ne donne le résultat souhaité

---

Mais putain parcours entre où et où ???????

Citation:

---

Envoyé par Petrucheqa

( le fait que les deux tableaux soient pas de la même taille me gène)

---

Je vois pas en quoi ça devait être génant. T'as une petite matrice (9 cases) qui recouvre une zone identique (9 cases) de la grande matrice. Quand, sur la grande matrice, t'as le X de la petite en position (par exemple) 3, 3, alors tu iras regarder les positions (2, 2), (2, 3), (2, 4), (3, 2), (3, 4), (4, 2), (4, 3) et (4, 4). Il n'y a rien de génant...

En fait j'ai trouvé une technique :D, merci pour le temps passé à répondre à mes questions !

Bonne continuation ;)