matrice d'adjacence à partir d'un tableau 2D
Je voudrais implémenter un algorithme qui me donnerait la matrice d'adjacence checkpoints (A, B, C, etc.) à partir d'un labyrinthe stocké dans un tableau char [] []
Ma première idée était d'utiliser un algorithme DFS pour déterminer si une paire checkpoint donnée était adjacente.
Mais après avoir été bloqué depuis 3 jours pour le mettre en œuvre (je suis un débutant), j'aimerais savoir si BFS est le meilleur moyen de résoudre ce problème.
Et si non, quelle serait une implémentation appropriée? Merci.
Voici un exemple de labyrinthe où # représente les murs et. représentent les pas (c.-à-d. deux étapes sont nécessaires pour pas de A à B donc l'edge entre A et B vaut 2):
Code:
1
2
3
4
5
6
7
8
9
10
11
| # A # # # # # #
# . # # # # # #
# B . . . C D #
# . # # # . # #
# E F # # . # #
# . # # # . # #
# G . . . H . I
# . # # # # # #
# . # # K # # #
# . . . J . L #
# # # # # # # # |
