/* Parcours d'un labyrinthe                    */

public class ParcoursLabyrinthe {
  
  static class Position {
    int l = -1;
    int c = -1; };
  
/////////////////////////////////////////////////

/* Fonction recursive de parcours              */
/* d'un labyrinthe avec affichage              */
/* des coordonnees des cellules                */

  static void parcours(boolean [][] lb,int lo,int co,int l,int c) {
    if ( lb[l][c] ) {
      Ecran.afficherln(l," ",c);
      if ( ( l-1 != lo ) || ( c != co ) ) {
        parcours(lb,l,c,l-1,c); }
      if ( ( l+1 != lo ) || ( c != co ) ) {
        parcours(lb,l,c,l+1,c); }
      if ( ( l != lo ) || ( c-1 != co ) ) {
        parcours(lb,l,c,l,c-1); }
      if ( ( l != lo ) || ( c+1 != co ) ) {
        parcours(lb,l,c,l,c+1); } }
  }

/* Fonction recursive de calcul de la longueur */
/* d'un labyrinthe                             */

  static int longueur(boolean [][] lb,Position po,Position p) {
    int lng = 0;
    Position ps = new Position();
    if ( lb[p.l][p.c] ) {
      lng = 1;
      if ( ( p.l-1 != po.l ) || ( p.c != po.c ) ) {
        ps.l = p.l-1;
        ps.c = p.c;
        lng = lng+longueur(lb,p,ps); }
      if ( ( p.l+1 != po.l ) || ( p.c != po.c ) ) {
        ps.l = p.l+1;
        ps.c = p.c;
        lng = lng+longueur(lb,p,ps); }
      if ( ( p.l != po.l ) || ( p.c-1 != po.c ) ) {
        ps.l = p.l;
        ps.c = p.c-1;
        lng = lng+longueur(lb,p,ps); }
      if ( ( p.l != po.l ) || ( p.c+1 != po.c ) ) {
        ps.l = p.l;
        ps.c = p.c+1;
        lng = lng+longueur(lb,p,ps); } }
    return lng;
  }

/* Fonction recursive de calcul de la distance */
/* maximale aux noeuds terminaux               */
/* d'un labyrinthe                             */

  static int distanceMax(boolean [][] lb,int lo,int co,int l,int c) {
    int dst = 0;
    int dtf;
    int dMax = 0;
    if ( lb[l][c] ) {
      if ( ( l-1 != lo ) || ( c != co ) ) {
        dtf = distanceMax(lb,l,c,l-1,c);
        if ( dtf > dMax ) {
          dMax = dtf; } }
      if ( ( l+1 != lo ) || ( c != co ) ) {
        dtf = distanceMax(lb,l,c,l+1,c);
        if ( dtf > dMax ) {
          dMax = dtf; } }
      if ( ( l != lo ) || ( c-1 != co ) ) {
        dtf = distanceMax(lb,l,c,l,c-1);
        if ( dtf > dMax ) {
          dMax = dtf; } }
      if ( ( l != lo ) || ( c+1 != co ) ) {
        dtf = distanceMax(lb,l,c,l,c+1);
        if ( dtf > dMax ) {
          dMax = dtf; } }
      dst = 1+dMax; }
    return dst;
  }

/* Recherche du nombre de voisins a vrai       */
/* d'une cellule                               */
  
  static int nombreVoisins(boolean [][] lb,int l,int c) {
    int res = 0;
    if ( lb[l+1][c] )
      res++;
    if ( lb[l-1][c] )
      res++;
    if ( lb[l][c-1] )
      res++;
    if ( lb[l][c+1] )
      res++;
    return res;
  }

/* Fonction recursive de recherche             */
/* des cellules terminales d'un labyrinthe     */
  
  static void rechercheCellulesTerminales(boolean [][] lb,int lo,int co,int l,int c) {
    if ( lb[l][c] ) {
      if ( nombreVoisins(lb,l,c) == 1 ) {
        Ecran.afficherln(l," ",c); }
        else {
        if ( ( l-1 != lo ) || ( c != co ) ) {
          rechercheCellulesTerminales(lb,l,c,l-1,c); }
        if ( ( l+1 != lo ) || ( c != co ) ) {
          rechercheCellulesTerminales(lb,l,c,l+1,c); }
        if ( ( l != lo ) || ( c-1 != co ) ) {
          rechercheCellulesTerminales(lb,l,c,l,c-1); }
        if ( ( l != lo ) || ( c+1 != co ) ) {
          rechercheCellulesTerminales(lb,l,c,l,c+1); } } }
  }

/* Fonction recursive de recherche             */
/* des cellules terminales d'un labyrinthe     */
  
  static int elongation(boolean [][] lb,int lo,int co,int l,int c,int max) {
    int res = max;
    int v;
    if ( lb[l][c] ) {
      if ( nombreVoisins(lb,l,c) == 1 ) {
        v = distanceMax(lb,-1,-1,l,c);
        if ( v > res )
          res = v; }
        else {
        if ( ( l-1 != lo ) || ( c != co ) ) {
          v = elongation(lb,l,c,l-1,c,res);
          if ( v > res )
            res = v; }
        if ( ( l+1 != lo ) || ( c != co ) ) {
          v = elongation(lb,l,c,l+1,c,res);
          if ( v > res )
            res = v; }
        if ( ( l != lo ) || ( c-1 != co ) ) {
          v = elongation(lb,l,c,l,c-1,res);
          if ( v > res )
            res = v; }
        if ( ( l != lo ) || ( c+1 != co ) ) {
          v = elongation(lb,l,c,l,c+1,res);
          if ( v > res )
            res = v; } } }
    return res;
  }

/* Amorcage du parcours d'un labyrinthe        */

  static void parcours(boolean [][] lb,int l,int c) {
    parcours(lb,-1,-1,l,c);
  }

/* Amorcage du calcul de la longueur           */
/* d'un labyrinthe                             */

  static int longueur(boolean [][] lb,Position p) {
    Position po = new Position();
    return longueur(lb,po,p);
  }

/* Amorcage du calcul de la distance maximale  */
/* aux noeuds terminaux d'un labyrinthe        */

  static int distanceMax(boolean [][] lb,Position p) {
    return distanceMax(lb,-1,-1,p.l,p.c);
  }

/* Amorcage de la recherche des cellules       */
/* terminales d'un labyrinthe                  */

  static void rechercheCellulesTerminales(boolean [][] lb,Position p) {
    rechercheCellulesTerminales(lb,-1,-1,p.l,p.c);
  }

/* Amorcage du calcul de l'elongation          */
/* d'un labyrinthe                             */

  static int elongation(boolean [][] lb,Position p) {
    return elongation(lb,-1,-1,p.l,p.c,0);
  }

/* Generation d'un nombre entier par tirage    */
/* au sort entre 1 et n inclus                 */
  static int nombreAleatoire(int n) {
    return(1+(int)(Math.random()*n));
  }
  
/* Creation d'un nouveau labyrinthe            */
/* par generation aleatoire                    */
  
  static boolean [][] nouveauLabyrinthe(int nl,int nc) {
    boolean [][] lb = new boolean[nl][nc];
    int l = nombreAleatoire(nl-2);
    int c = nombreAleatoire(nc-2);
    int cpt = 1;
    lb[l][c] = true;
    while ( cpt < (nl-2)*(nc-2)/2 ) {
      l = nombreAleatoire(nl-2);
      c = nombreAleatoire(nc-2);
      if ( !lb[l][c] && ( nombreVoisins(lb,l,c) == 1 ) ) {
        cpt++;
        lb[l][c] = true; } }
    Ecran.afficherln(cpt);
    return(lb);
  }
  
/* Determination d'une position a vrai         */
/* d'un labyrinthe                             */
  
  static Position trouvePositionDepart(boolean [][] lb) {
    Position p = new Position();
    do {
      p.l = nombreAleatoire(lb.length-2);
      p.c = nombreAleatoire(lb[0].length-2); }
    while ( !lb[p.l][p.c] );
    return(p);
  }
  
/////////////////////////////////////////////////
  
/* Affichage d'un labyrinthe                   */

  static void affichage(boolean [][] tb) {
    for ( int i = 0 ; i < tb.length ; i++ ) {
      for ( int j = 0 ; j < tb[i].length ; j++ ) {
        if ( tb[i][j] )
          Ecran.afficher('V');
          else
          Ecran.afficher('F'); }
      Ecran.sautDeLigne(); }
  }
  
/* Programme principal                         */

  public static void main(String [] args) {
    Position init;
/*    boolean [][] lb1 = { { false,false,false,false,false,false,false,false,false,false,false,false },
                         { false,false, true, true, true,false,false, true, true, true,false,false },
                         { false,false,false,false, true, true, true, true,false, true,false,false },
                         { false, true, true,false, true,false,false, true,false, true, true,false },
                         { false,false, true, true, true,false, true, true,false,false, true,false },
                         { false, true, true,false, true,false, true,false, true, true, true,false },
                         { false,false,false,false,false,false,false,false,false,false,false,false } };
    Ecran.sautDeLigne();
    affichage(lb1);
    Ecran.sautDeLigne();
    init = trouvePositionDepart(lb1);
    Ecran.afficherln(init.l," ",init.c);
    Ecran.sautDeLigne();
    Ecran.afficherln(longueur(lb1,init));
    Ecran.sautDeLigne();
    Ecran.afficherln(distanceMax(lb1,init));
    Ecran.sautDeLigne();
    rechercheCellulesTerminales(lb1,init);
    Ecran.sautDeLigne();
    Ecran.afficherln(elongation(lb1,init));
    Ecran.sautDeLigne();
    parcours(lb1,3,1);
    Ecran.sautDeLigne();*/
/*    boolean [][] lb2 = nouveauLabyrinthe(30,50);
    affichage(lb2);
    Ecran.sautDeLigne();
    init = trouvePositionDepart(lb2);
    Ecran.afficherln(init.l," ",init.c);
    Ecran.sautDeLigne();
    Ecran.afficherln(longueur(lb2,init));
    Ecran.sautDeLigne();
    Ecran.afficherln(distanceMax(lb2,init));
    Ecran.sautDeLigne();
    rechercheCellulesTerminales(lb2,init);
    Ecran.sautDeLigne();
    Ecran.afficherln(elongation(lb2,init));*/
    boolean [][] lb3 = nouveauLabyrinthe(500,500);
    Ecran.sautDeLigne();
    init = trouvePositionDepart(lb3);
    Ecran.afficherln(init.l," ",init.c);
    Ecran.sautDeLigne();
    Ecran.afficherln(longueur(lb3,init));
    Ecran.sautDeLigne();
    Ecran.afficherln(distanceMax(lb3,init));
    Ecran.sautDeLigne();
    Ecran.afficherln(elongation(lb3,init));
  }
}