import fr.upd.*;
import java.util.*;

class Point {
  public int x;
  public int y;
  public Point(int x,int y) { this.x = x; this.y = y; }
  public String toString() {
    return "("+x+","+y+")";
  }
}

public class Lab {
  public static final int COULOIR = 0;
  public static final int MUR = 1;
  public static final int CAILLOU = 2;
    public static int[][] lab = {
    { 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
    { 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
    { 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1 },
    { 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0 },
    { 1, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1 },
    { 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
    { 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
    { 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1 },
    { 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1 },
    { 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1 },
    { 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1 },
    { 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1 },
    { 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1 },
    { 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1 },
    { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1 },
  };
  public static final int TAILLE = 30;
  public static int nSolutions;

  public static void affiche() {
    for (int y=0; y<lab.length; y++) {
      for (int x=0; x<lab.length; x++) {
        switch (lab[y][x]) {
        case COULOIR:
          Facile.setColor(255,255,255);
          break;
        case MUR:
          Facile.setColor(0,0,0);
          break;
        case CAILLOU:
          Facile.setColor(0,255,0);
          break;
        }
        Facile.fillRect(x*TAILLE,y*TAILLE,TAILLE,TAILLE);
      }
    }
    Facile.sleep(10);
  }
  
  public static Vector<Stack<Point>> solutions;
  
  public static boolean parcours(int x,int y,Stack<Point> chemin) {
    if (x<0 || x>=lab.length || y<0 || y >= lab.length) {
      nSolutions++;
      // on enregistre dans l'ensemble des solutions une copie du
      // chemin qui nous a mené ici
      solutions.add((Stack<Point>)chemin.clone());
      return true;
    }
    if (lab[y][x]==CAILLOU || lab[y][x]==MUR) return false;
    lab[y][x] = CAILLOU;
    chemin.push(new Point(x,y));
    affiche();
    boolean b = false;
    // à gauche
    //    if (parcours(x-1,y)) return true;
    b |= parcours(x-1,y,chemin);
    // à droite
    //    if (parcours(x+1,y)) return true;
    b |= parcours(x+1,y,chemin);
    // en haut
    //    if (parcours(x,y-1)) return true;
    b |= parcours(x,y-1,chemin);
    // en bas
    //    if (parcours(x,y+1)) return true;
    b |= parcours(x,y+1,chemin);
    lab[y][x] = COULOIR;
    affiche();
    chemin.pop();
    return b;
  }
  public static void main(String[] args) {
    Facile.startDrawings(TAILLE*lab.length,TAILLE*lab.length);
    nSolutions = 0;
    solutions = new Vector<Stack<Point>>();
    Stack<Point> chemin = new Stack<Point>();
    boolean b = parcours(8,7,chemin);
    if (b) {
      System.out.println("Il y a "+nSolutions+" façons de sortir");
      for (Stack<Point> c : solutions) {
        System.out.println(c);
      }
    }
    else System.out.println("Pas de sortie");
  }
}