#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <stdlib.h>

using namespace std;



/*------------------------------------------------------------------------------
 *              Représentation classique du labyrinthe
 *------------------------------------------------------------------------------
 *  Ce code provient du TP2, il représente un labyrinthe comme un vecteur de
 *  vecteur de caractère. Il n'est pas nécessaire de s'intéresser aux détails
 *  des fonctions ci-dessous, mais il faut quand même se rappeler de comment
 *  accéder aux cases du labyrinthe.
 *----------------------------------------------------------------------------*/

// Caractères représentant le labyrinthe
char MUR     = '#' ;
char VIDE    = ' ' ;
char ENCOURS = '?' ;
char IMPASSE = '@' ;
char CHEMIN  = 'O' ;

// Définition du type Labyrinthe
typedef vector<vector<char> > Labyrinthe ;

// Création d'un labyrinthe
Labyrinthe create(int tX, int tY)
  {
  Labyrinthe laby ;
	for (int j = 0 ; j < 2 * tY + 1 ; j++)
    {
		vector<char> v(2 * tX + 1) ;
		laby.push_back(v) ;
		for (int i = 0; i < 2 * tX + 1; i++)
			laby[j][i] = (i % 2 == 1 && j % 2 == 1) ? ENCOURS : MUR ;
	  }
	int cpt = tX * tY - 1 ;
	int x = 2 * tX - 1, y = 2 * tY - 1, xx, yy ;
	laby[y][x] = VIDE ;
	int alea ;
	while (cpt > 0)
    {
		xx = x ;
		yy = y ;
		alea = rand() % 4 ;
		switch (alea)
      {
			case 0 :
				if (x > 1) x -= 2 ;
				break ;
			case 1 :
				if (y > 1) y -= 2 ;
				break ;
			case 2 :
				if (x < 2 * tX - 1 - 1) x += 2 ;
				break ;
			default :
				if (y < 2 * tY - 1 - 1) y += 2 ;
  		}
		if (laby[y][x] == ENCOURS)
      {
			cpt-- ;
			laby[y][x] = VIDE ;
			laby[(y + yy) / 2][(x + xx) / 2] = VIDE ;
  		}
  	}
	laby[0][1] = VIDE ;
	laby[2 * tY - 1][2 * tX] = VIDE ;
  return laby ;
  }

// Affichage d'un labyrinthe
void print(Labyrinthe& laby)
  {
	cout << " E" << endl ;
	cout << " n" << endl ;
	cout << " t" << endl ;
	cout << " r" << endl ;
	cout << " e" << endl ;
	cout << " e" ;
	for (int j = 0 ; j < laby.size() - 1 ; j++)
    {
		cout << endl ;
		for (int i = 0 ; i < laby[j].size() ; i++)
			cout << laby[j][i] ;
  	}
	cout << "Sortie"<<endl ;
	for (int i = 0 ; i < laby[laby.size() - 1].size() ; i++)
		cout << laby[laby.size() - 1][i] ;
	cout <<endl ;
  }

// Remets toutes la case ENCOURS à VIDE
void clean (Labyrinthe& laby)
  {
  for (int j = 0 ; j < laby.size() ; j++)
    for (int i = 0 ; i < laby[j].size() ; i++)
      if (laby[j][i] == ENCOURS)
        laby[j][i] = VIDE ;
  }



/*------------------------------------------------------------------------------
 *                  Arbre des chemins du labyrinthe
 *------------------------------------------------------------------------------
 *  C'est ici que vous entrez en scène. On vous demande d'implémenter quelques
 *  fonctions autour d'une structure d'arbre ou chaque noeud correspond à une
 *  case du labyrinthe.
 *----------------------------------------------------------------------------*/

// Nombre de fils possible d'un noeud
const int NBFILS = 3 ;

// Structure de données. Chaque noeud peut avoir jusqu'à trois fils (il ne peut
// pas y avoir plus de trois chemins partant d'un noeud vu qu'on est arrivé à
// ce noeud au travers d'une des quatres entrées (nord, sud, est, ouest).
struct Noeud
  {
  int x ;   // Coordonnée en x de la case représentée
  int y ;   // Coordonnée en y de la case représentée
  struct Noeud * fils[NBFILS] ; // Chaque case de ce tableau représente un fils
  } ;

// Crée un nouveau noeud correctement initialisé
Noeud* construireNoeud(int x, int y)
  {
  Noeud* n = (Noeud*)malloc(sizeof(Noeud)) ;
  n->x = x ; n->y = y ;
  for (int i = 0 ; i < NBFILS ; i++)
    n->fils[i] = NULL ;
  return n ;
  }

// Fonction d'affichage d'un noeud
void afficheNoeud(Noeud* n)
  {
  if (n != NULL)
    cout << "(" << n->x << ", " << n->y << ")" ;
  else
    cout << "(NULL)" ;
  }


// Première fonction à implémenter : Construire l'arbre représentant un
// labyrinthe. Cette fonction est récursive naturellement. N'hésitez pas à
// marquer les cases du labyrinthe déjà visitées avec le caractère ENCOURS.
Noeud* construireArbre(Labyrinthe& laby, int x, int y)
  {
  Noeud* arbre = NULL ;
  // TODO : Implémentez ici

  // Nettoyage du labyrinthe et retour
  clean(laby) ;
  return arbre ;
  }

// Deuxième fonction à implémenter : Calculer la profondeur de l'arbre. La
// profondeur d'un arbre correspond aux nombres de noeud à traverser pour
// atteindre celui qui est le plus éloigné de la racine. La récursion s'arrête
// si le pointeur d'entrée est NULL, la profondeur est dans ce cas de zéro.
int profondeurArbre(Noeud* n)
  {
  if (n != NULL)
    {
    // TODO
    }
  return 0 ;
  }

// Troisième fonction à implémenter : Afficher les impasses du labyrinthe,
// c'est à dire les noeuds n'ayant aucun fils. On fournit une fonction
// affichant un message décrivant le noeud en entrée comme une impasse.
void messageImpasse(Noeud* n)
  {
  cout << "\t* " ;
  afficheNoeud(n) ;
  cout << endl ;
  }

void afficheImpasses(Noeud* n)
  {
  // TODO
  }

// Quatrième et dernière fonction à implémenter : Trouver l'impasse la plus
// proche de l'entrée. On utilisera pour ça un parcours en largeur. On fournit
// pour se faire trois fonction qui manipule une file d'attente
typedef queue<Noeud*>* File ;
File empty()
  {
  File f = new queue<Noeud*>() ;
  return f ;
  }

void push(Noeud* n, File f)
  { f->push(n) ; }

Noeud* pop(File f)
  {
  Noeud * n = f->front() ;
  f->pop() ;
  return n ;
  }

Noeud* plusProcheImpasse(Noeud* n)
  {
  Noeud* impasse = NULL ;
  // TODO
  return impasse ;
  }



/*------------------------------------------------------------------------------
 *    Test des fonctions. Vous n'avez rien à modifier.
 *----------------------------------------------------------------------------*/
int main()
  {
  // On fixe la graine pour que tout le monde est le même labyrinthe
	srand(42) ;
  // On crée et on affiche un nouveau labyrinthe
	Labyrinthe laby = create(14, 14) ;
  print(laby) ;
  // On construit l'arbre associé
  Noeud* t = construireArbre(laby, 1, 0) ;
  // On affiche sa profondeur
  cout << "La profondeur de l'arbre est de " << profondeurArbre(t) << endl ;
  // On affiche les impasses
  cout << "Voici les impasses du labyrinthe :" << endl ;
  afficheImpasses(t) ;
  // On affiche la plus proche
  Noeud* n = plusProcheImpasse(t) ;
  cout << "La plus proche est " ;
  afficheNoeud(n) ;
  cout << endl ;
	return 0;
  }