TD No 2
from http://vernier.frederic.free.fr/Teaching/PimpA

Recursivité

Copier le code suivant dans un projet C++ Code::Block, compilez et éxécutez.

// compile avec g++ main.cpp -o main.out
#include <iostream>
#include <fstream>
#include <vector>
#include <stdlib.h>
using namespace std;


char MUR     = '#';
char VIDE    = ' ';
char ENCOURS = '?';
char IMPASSE = '@';
char CHEMIN  = 'O';

typedef vector<vector<char> > Labyrinthe;
Labyrinthe laby;


/**
 * initialize le labyrinthe avec juste des colonnes pour soutenir le plafond !
 */
void initLayrinthe0(int tX, int tY) {
  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++){
      char c;
      if (i%2==1  && j%2==1)
        c = ENCOURS;
      else
        c = MUR;
      laby[j][i] = c;
    }
  }

  for(int j=1; j<2*tY-0; j++){
    for(int i=1; i<2*tX-0; i++){
      if (i%2==0  && j%2==0)
         laby[j][i] = MUR;
      else
         laby[j][i] = VIDE;
    }
  }

  laby[0][1] = VIDE;
  laby[2 * tY - 1][2 * tX] = VIDE;
}

/**
 * initialize le labyrinthe en creant une serie
 * de salles non reliees puis en percant des murs
 * au hasard du parcours d'un fantome qui troue
 * les murs si et seulement si il arrive dans une
 *salle inexploree
 */
void initLayrinthe1(int tX, int tY) {
  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++){
      char c;
      if (i%2==1  && j%2==1)
        c = ENCOURS;
      else
        c = MUR;
      laby[j][i] = c;
    }
  }
  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; // la salle inexploree devient exploree
      laby[(y + yy) / 2][(x + xx) / 2] = VIDE; // le mur entre cette salle et d'ou on vient est perce
    }
  }
  laby[0][1] = VIDE;
  laby[2 * tY - 1][2 * tX] = VIDE;
}


/**
 * Affiche le labyrinthe "ligne par ligne"
 **/
void dispLayrinthe(){
  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;
}


/**
 * Cherche un chemin en "quasi diagonale"
 **/
bool chercheChemin0(){
  int x = 1;
  int y = 1;
  laby[y][x] = CHEMIN;
  while (x!=laby[laby.size()-2].size()-2 && y!=laby.size()-2) {
    if (laby[y][x+1]==VIDE && laby[y][x+2]==VIDE && laby[y+1][x+2]==VIDE && laby[y+2][x+2]==VIDE) {
      laby[y][x+1]=CHEMIN;
      laby[y][x+2]=CHEMIN;
      laby[y+1][x+2]=CHEMIN;
      laby[y+2][x+2]=CHEMIN;
      x=x+2;
      y=y+2;
    } else return false;
  }
  return true;
}


int main(int, char*[]) {
  initLayrinthe1(14, 14);
  dispLayrinthe();

  if (chercheChemin0())
    cout << endl << "TROUVE !" << endl << endl;
  else
    cout << endl << "PAS TROUVE !" << endl << endl;

  dispLayrinthe();

  return 0;
}

Questions sans code à écrire

1. Lire le code. Y a t-il une fonction résursive dans ce code ?
2. A quoi servent les fonctions initLayrinthe0() et initLayrinthe1() ?
3. Proposez une fonction qui initialise le labyrinthe uniquement dans une sous-partie x1->x2 et y1->y2.
4. Proposez un algorithme pour initialiser le labyrinthe dans les 4 sous-parties disjointes puis qui "ouvre" des murs entre les parties.
5. Proposez une stratégie récursive globale et explicitez le/les cas de base.

Implémentations

6. Codez une fonction récursive pour rechercher si un chemin existe
7. Codez une fonction récursive qui recherche toutes cases qui sont reliées à la sortie
   • ... qui marque les endroits ou on est deja passés
   • ... qui nettoie les endroits parcourus
   • ... qui affiche le chemin trouvé
8. Codez une fonction qui "bouche" des murs TANT QUE on trouve un chemin entre l'entrée et la sortie

Questions sans code à écrire

1. Votre algorithme de recherche de chemin trouve t-il le plus court chemin ?
2. Proposez une stratégie pour trouver le plus court chemin
3. Que faudrait-il changer pour chercher un chemin dans un labyrinthe en 3 dimensions ?