Bonjour,

Je dispose d'un tableau de case à 2 dimensions (n*n) dont chaque case peut, ou non, acceder à chacune de ses voisines. En supposant une case de départ spécifiée, je voudrais déterminer tous les "chemins" possibles à partir de cette case.

Pour "stocker" ces chemins je pensais faire un arbre ou un tableau de chemins (les 2 possibilités m'intéressent, mais l'arbre serait optimal).

Je sens que c'est très obscur alors voilà un exemple :

Soit le tableau 4*4 de dont les cases sont notées de A à P.
On se donne comme case initiale la case G.
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
+-----+-----+-----+-----+    +-----+-----+-----+-----+
|     |     |     |     |    |     |     |     |     |
|  A  |  B 1|1 C 1|1 D  |    |  A  |  B-----C-----D  |
|  1  |  1  |  1  |     |    |  |  |  |  |  |  |     |
+-----+-----+-----+-----+    +--|--+--|--+--|--+-----+
|  1  |  1  |  1  |     |    |  |  |  |  |  |  |     |
|  E 1|1 F  |  G 1|1 H  |    |  E-----F  |  G-----H  |
|     |     |  1  |  1  |    |     |     |  |  |  |  |
+-----+-----+-----+-----+ => +-----+-----+--|--+--|--+
|     |     |  1  |  1  |    |     |     |  |  |  |  |
|  I 1|1 J 1|1 K  |  L  |    |  I-----J-----K  |  L  |
|     |  1  |     |     |    |     |  |  |     |     |
+-----+-----+-----+-----+    +-----+--|--+-----+-----+
|     |  1  |     |     |    |     |  |  |     |     |
|  M 1|1 N  |  O  |  P  |    |  M-----N  |  O  |  P  |
|     |     |     |     |    |     |     |     |     |
+-----+-----+-----+-----+    +-----+-----+-----+-----+
En supposant connue une "operation" ( l'operation "=" par exemple) permettant de savoir si une case est accessible (en fonction de son nom OU de sa direction) à partir de la case actuelle, je voudrais pouvoir créer un arbre ou un tableau listant les "plus longs" chemins possibles.

Le tableau des chemins de l'exemple précédent serait :
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
[ [G, C, B, F, E, A] ;
  [G, C, D] ;
  [G, K, J, N, M] ;
  [G, K, J, I] ;
  [G, H, L] ]
Pour l'arbre je pense qu'il est aussi simple à "voir".

Ce que je n'arrive pas à faire, c'est trouver un algo qui permette de construire ce tableau/arbre à partir de la case donnée.

Donc si vous voyez comment faire, toute idée est la bienvenue.

PS : le but de ce tableau/arbre est d'être lu uniquement. Après construction il n'y aura ni ajout ni suppression d'élément.

Merci d'avance,
Loceka.