/* Parcours dans une matrice de booleen        */

public class ParcoursMatrice {

  static int nombreAleatoire(int max) {
    return((int) (max*Math.random()));
  }
  
/* Methode de creation d'une matrice           */
/* d'entiers aleatoires compris entre 1 et 5   */

  static int [][] initMatricePointsDeplacement(int colonnes,int lignes) {
    int [][] tab = new int[lignes][colonnes];
    for ( int l = 0 ; l < tab.length ; l = l+1 ) {
      for ( int c = 0 ; c < tab[l].length ; c = c+1 ) {
        tab[l][c] = 1; } }
    for ( int i = 0 ; i < 150 ; i++ ) {
      tab[nombreAleatoire(lignes)][nombreAleatoire(colonnes)] = 1+nombreAleatoire(5); }
    return tab;
  }

  static void cercle(int px,int py,int r,boolean [][] t) {
    int dx;
    int dy;
    for ( int l = 0 ; l < t.length ; l = l+1 ) {
      for ( int c = 0 ; c < t[l].length ; c = c+1 ) {
        dx = px-c;
        dy = py-l;
        if ( dx*dx+dy*dy < r*r ) {
          t[l][c] = true; } } }
  }

/* Methode de creation d'une matrice           */
/* de booleen a faux initialisee               */
/* avec deux cercles de booleens a vrai        */

  static boolean [][] initMatrice(int colonnes,int lignes) {
    boolean [][] tab = new boolean[lignes][colonnes];
    cercle(5,5,4,tab);
    cercle(14,6,4,tab);
    return tab;
  }

/* Methode d'affichage des valeurs contenues   */
/* dans une matrice de booleen                 */
  
  static void affichageMatrice(boolean [][] t) {
    int i;
    int j;
    for ( i = 0 ; i < t.length ; i = i+1 ) {
      for ( j = 0 ; j < t[i].length ; j = j+1 ) {
        if ( t[i][j] ) {
          Ecran.afficher("  X"); }
          else {
          Ecran.afficher("  O"); } }
      Ecran.sautDeLigne(); }
  }

/* Methode d'affichage d'un entier             */
/* sur l caracteres de large                   */
  
  static void afficher(int v,int l) {
    int i;
    int val;
    val = v;
    int nbc = 0;
    if ( v != 0 ) {
      while ( val != 0 ) {
        nbc = nbc+1;
        val = val/10; } }
      else {
      nbc = 1; }
    if ( v < 0 ) {
      nbc = nbc+1; }
    for ( i = 0 ; i < l-nbc ; i = i+1 ) {
      Ecran.afficher(" "); }
    Ecran.afficher(v);
  }

/* Methode d'affichage des valeurs contenues   */
/* dans une matrice de int                     */
  
  static void affichageMatrice(int [][] t) {
    int i;
    int j;
    for ( i = 0 ; i < t.length ; i = i+1 ) {
      for ( j = 0 ; j < t[i].length ; j = j+1 ) {
        afficher(t[i][j],3); }
      Ecran.sautDeLigne(); }
  }

/////////////////////////////////////////////////
  
/* Calcul de la matrice des distances          */
/* "a vol d'oiseau"                            */

  static int [][] matriceDesDistances(int px,int py,int nl,int nc) {
    int i;
    int j;
    int [][] md = new int[nl][nc];
    for ( i = 0 ; i < nl ; i = i+1 ) {
      for ( j = 0 ; j < nc ; j = j+1 ) {
        md[i][j] = Math.abs(i-py)+Math.abs(j-px); } }
    return md;
  }

/* Calcul de la matrice des distances          */
/* "avec obstacles sur le passage"             */
  
  static boolean voisin(int x,int y,int [][] md,int distance) {
    boolean res = false;
    if ( ( x >= 0 ) && ( x < md[0].length ) &&
         ( y >= 0 ) && ( y < md.length ) ) {
      if ( md[y][x] == distance) {
        res = true; } }
    return res;
  }

  static boolean voisinage(int c,int l,int [][] md,int distance,
                           boolean [][] t,boolean v) {
    boolean res = false;
    if ( ( md[l][c] == -1 ) && ( t[l][c] == v ) ) {
      if ( voisin(c+1,l,md,distance) ) {
        res = true; }
        else {
        if ( voisin(c-1,l,md,distance) ) {
          res = true; }
          else {
          if ( voisin(c,l+1,md,distance) ) {
            res = true; }
            else {
            if ( voisin(c,l-1,md,distance) ) {
              res = true; } } } } }
    return res;
  }

  static int [][] distances(int px,int py,boolean [][] t) {
    int i;
    int j;
    int l;
    int c;
    int nl = t.length;
    int nc = t[0].length;
    boolean change;
    int distance = 0;
    int [][] md = new int[nl][nc];
    for ( i = 0 ; i < nl ; i = i+1 ) {
      for ( j = 0 ; j < nc ; j = j+1 ) {
        md[i][j] = -1; } }
    md[py][px] = 0;
    do {
      change = false;
      for ( l = 0 ; l < nl ; l = l+1 ) {
        for ( c = 0 ; c < nc ; c = c+1 ) {
          if ( voisinage(c,l,md,distance,t,t[py][px]) ) {
            change = true;
            md[l][c] = distance+1; } } }
      distance = distance+1; }
    while ( change );
    return md;
  }

  static void ajusteVoisin(int [][] tp,boolean [][] tpa,int [][] md,int c,int l,int dst,int distance) {
    if ( ( c >= 0 ) && ( c < md[0].length ) &&
         ( l >= 0 ) && ( l < md.length ) ) {
      int dt = dst+tp[l][c];
      if ( ( md[l][c] == -1 ) && ( dt <= distance ) ) {
        tpa[l][c] = true;
        md[l][c] = dt; } }
  }

  static void ajusteVoisinage(int [][] tp,boolean [][] tpa,int [][] md,int c,int l,int distance) {
    ajusteVoisin(tp,tpa,md,c+1,l,md[l][c],distance);
    ajusteVoisin(tp,tpa,md,c-1,l,md[l][c],distance);
    ajusteVoisin(tp,tpa,md,c,l-1,md[l][c],distance);
    ajusteVoisin(tp,tpa,md,c,l+1,md[l][c],distance);
  }
  
  static boolean [][] positionsAtteignables(int [][] tp,int px,int py,int dist) {
    int i;
    int j;
    int l;
    int c;
    int nl = tp.length;
    int nc = tp[0].length;
    boolean [][] tpa = new boolean[nl][nc];
    int [][] md = new int[nl][nc];
    for ( i = 0 ; i < nl ; i = i+1 ) {
      for ( j = 0 ; j < nc ; j = j+1 ) {
        md[i][j] = -1; } }
    md[py][px] = 0;
    tpa[py][px] = true;
    for ( int distance = 0 ; distance < dist ; distance++ ) {
      for ( l = 0 ; l < nl ; l = l+1 ) {
        for ( c = 0 ; c < nc ; c = c+1 ) {
          if ( md[l][c] == distance )
            ajusteVoisinage(tp,tpa,md,c,l,dist); } } }
    affichageMatrice(md);
    Ecran.sautDeLigne();
    return tpa;
  }
  
/////////////////////////////////////////////////
  
/* Programme principal                         */

  public static void main(String [] args) {
    boolean [][] t = initMatrice(20,14);
    affichageMatrice(t);
    int [][] md = matriceDesDistances(8,5,14,20);
    Ecran.sautDeLigne();
    affichageMatrice(md);
    int [][] d1 = distances(8,5,t);
    Ecran.sautDeLigne();
    affichageMatrice(d1);
    int [][] d2 = distances(1,8,t);
    Ecran.sautDeLigne();
    affichageMatrice(d2);
    Ecran.sautDeLigne();
    int [][] tp = initMatricePointsDeplacement(20,14);
    affichageMatrice(tp);
    Ecran.sautDeLigne();
    boolean [][] ta = positionsAtteignables(tp,10,7,9);
    affichageMatrice(ta);
  }
}