Plus court chemin labyrinthe

Bonjour, je dois réaliser le programme suivant en C++ :

La matrice comporte des noeuds de 5 types :
- Noeud vide : on peut se déplacer dedans. Ils doivent représenter environ 2/3 de la matrice. Ils sont représentés par un _.
- Noeud plein : on ne peut pas se déplacer dedans. Ils doivent représenter environ 1/3 de la matrice. Ils sont représentés par un X.
- Départ : l’algorithme de plus court chemin partira de ce noeud. Il n’y a qu’un et un seul noeud de ce type par matrice. Il est représenté par un D.
- Arrivée : l’algorithme de plus court chemin arrivera à ce noeud. Il n’y a qu’un et un seul noeud de ce type par matrice. Il est représenté par un A.
- Chemin : un noeud qui relie de départ et l’arrivée. Ils sont représentés par un *.
La matrice générée doit obligatoirement posséder un chemin entre de départ et l’arrivée. La taille de la matrice doit être passée en paramètre du programme.
Les déplacements sur la matrice ne se font pas en diagonale. Il se font uniquement dans 4 directions : haut, bas, gauche, droite.

Je sais que pour effectuer ce code je dois utiliser l'algorithme de Djikstra mais j'ai un peu de mal à commencer.
Des conseils ou des pistes ?

Merci

A* s'implémente en quelques minutes/heures en suivant l'algo.