import fr.upd.*;
import java.util.*;
/**
 * Un programme pour trouver la sortie dans un labyrinthe...
 * L'idée est d'utiliser une fonction récursive qui en un point donnée tente
 * toutes les possibilités (gauche, droite, haut, bas) en laissant un caillou
 * permettant d'éviter de boucler à l'infini dans le labyrinthe... Si en
 * se déplaçant on trouve un caillou ou un mur on abandonne et on revient
 * à la situation précédente depuis laquelle on essaie un autre choix.
 *
 * Exercice : modifier le code de sorte que le labyrinthe ne soit plus carré
 * Exercice : trouver un labyrinthe dans lequel l'algorithme de recherche
 *            parcours plusieurs fois certaines parties du labyrinthe
 * Exercice : modifier l'algorithme de façon à éviter que l'algorithme ne
 *            parcours plusieurs fois les mêmes parties inutiles du labyrinthe.
 *            (idée : programmation dynamique)
 * Exercice : modifier l'algorithme de sorte que l'on trouve TOUS les chemins
 *            possibles (et toutes les sorties).
 */
public class Labyrinthe {
  /**
   * Le labyrinthe est représenté sous la forme d'un tableau à deux dimensions.
   * Dans chaque case, on indique s'il y a la présence d'un mur (valeur 1) ou
   * rien (valeur 0). Les cailloux (il n'y en a pas au départ) seront
   * représentés par la valeur 2.
   */
  public static int [][] labi = {
    { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
    { 1, 1, 0, 0, 0, 0, 1, 1, 0, 0 },
    { 1, 1, 0, 1, 0, 1, 1, 0, 0, 1 },
    { 1, 0, 0, 1, 0, 0, 1, 0, 1, 1 },
    { 1, 0, 1, 0, 0, 1, 1, 0, 0, 1 },
    { 1, 0, 1, 1, 0, 1, 1, 1, 0, 1 },
    { 1, 0, 1, 1, 0, 0, 0, 0, 0, 1 },
    { 1, 0, 0, 0, 0, 1, 1, 1, 1, 1 },
    { 1, 0, 1, 1, 0, 0, 0, 0, 0, 1 },
    { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }
  };
  public static int TAILLE = 40;
  public static void affiche() {
    for (int i=0; i<labi.length; i++) {
      for (int j=0; j<labi.length; j++) {
        switch(labi[i][j]) {
        case 0: // Le vide est blanc
          Facile.setColor(255,255,255);
          Facile.fillRect(j*TAILLE,i*TAILLE,TAILLE,TAILLE);
          break;
        case 1: // Les murs sont noirs
          Facile.setColor(0,0,0);
          Facile.fillRect(j*TAILLE,i*TAILLE,TAILLE,TAILLE);
          break;
        case 2: // Les cailloux sont verts
          Facile.setColor(0,255,0);
          Facile.fillRect(j*TAILLE,i*TAILLE,TAILLE,TAILLE);
          break;
        }
      }
    }
    // On ralentit l'algorithme artifiellement afin de mieux voir ce
    // qui se passe
    Facile.sleep(500);
  }
  /**
   * Quelle décision prendre au point x,y ?
   */
  public static boolean resoud(int x,int y,Stack<String> chemin) {
    // Si on sort du tableau alors on est sorti du labyrinthe.
    // On revient sur nos pas en disant par ici c'était bon!
    if (x<0 || x>=labi.length || y<0 || y>=labi.length) return true;
    // Si on tombe sur un mur ou un caillou, on revient sur nos pas.
    // On revient sur nos pas en disant, par là c'est pas bon!
    if (labi[x][y]==1 || labi[x][y]==2) return false;
    // Ok, pas mur ni caillou, alors on laisse tomber un caillou
    labi[x][y] = 2;
    // On affiche l'état courant du parcours
    affiche();
    // Essayons vers le haut!
    // Si c'est bon, on enregistre le mouvement dans la solution
    if (resoud(x-1,y,chemin)) { chemin.push("haut"); return true; }
    // Essayons vers le bas!
    // Si c'est bon, on enregistre le mouvement dans la solution
    if (resoud(x+1,y,chemin)) { chemin.push("bas");  return true; }
    // Essayons vers la gauche!
    // Si c'est bon, on enregistre le mouvement dans la solution
    if (resoud(x,y-1,chemin)) { chemin.push("gauche"); return true; }
    // Essayons vers la droite!
    // Si c'est bon, on enregistre le mouvement dans la solution
    if (resoud(x,y+1,chemin)) { chemin.push("droite"); return true; }
    // Rien n'a fonctionné à partir d'ici, enlevons le caillou et
    // revenons sur nos pas...
    labi[x][y] = 0;
    affiche();
    return false;
  }
  public static void main(String []args) {
    // Au départ la solution est « vide »
    Stack<String> chemin = new Stack<String>();
    Facile.startDrawings(600,600);
    affiche();
    if (resoud(4,3,chemin)) {
      // Attention les mouvements sont récupérés « à l'envers »...
      System.out.println("ok la solution est "+chemin);
    } else {
      System.out.println("pas ok");
    }
  }
}