Solution du TD d'informatique No. 8 : Parcours simple de labyrinthe

Patrick Gros -- Patrick.Gros@irisa.fr
Didier Le Botlan -- didier.le_botlan@inria.fr

Lundi 15 janvier 2001

import java.io.* ;
import java.lang.* ;
import java.util.* ;

public class labyrinthe_simple {
  // Affichage graphique d'un graphe
  //////////////////////////////////
  static void Afficher_Graphe(Graphe graphe) {
    // Calcul de la taille du graphe
    int xmax = 0, ymax = 0 ;
    for (int i = 0 ; i < graphe.nb_sommets ; i++) {
      if (xmax < graphe.sommets[i].x)
        xmax = graphe.sommets[i].x ;
      if (ymax < graphe.sommets[i].y)
        ymax = graphe.sommets[i].y ;
    }

    // Ouverture de la fenetre graphique
    MacLib.ShowDrawing() ;
    Rect r = new Rect() ;
    r. top = 100 ;
    r.left = 100 ;
    r.bottom = (short)(r.top + ymax + 20) ;
    r.right = (short)(r.left + xmax + 20) ;
    MacLib.SetDrawingRect(r) ;

    // Dessin des sommets
    //for (int i = 0 ; i < graphe.nb_sommets ; i++) {
    //   MacLib.PaintCircle(graphe.sommets[i].x, graphe.sommets[i].y, 2) ;
    //  MacLib.MoveTo(graphe.sommets[i].x + 5, graphe.sommets[i].y + 5) ;
    //  MacLib.DrawString((new Integer(graphe.sommets[i].numero)).toString()) ;
    //}

    // Dessins des aretes
    for (int i = 0 ; i < graphe.nb_sommets ; i++)
      for (int j = 0 ; j < graphe.nb_sommets ; j++)
        if (graphe.aretes[i][j])
          MacLib.DrawLine(graphe.sommets[i].x, graphe.sommets[i].y, graphe.sommets[j].x, graphe.sommets[j].y) ;
  }

  // Dessin d'un chemin
  /////////////////////
  static void Afficher_Chemin(Graphe graphe, int [] chemin, int n) {
    MacLib.ForeColor(MacLib.redColor) ;
    for (int i = 0 ; i < n ; i++)
      MacLib.DrawLine(graphe.sommets[chemin[i]].x, graphe.sommets[chemin[i]].y,
                      graphe.sommets[chemin[i + 1]].x, graphe.sommets[chemin[i + 1]].y) ;
  }
  
  // Rechercher un chemin entre deux points par la methode du fil d'Ariane
  ////////////////////////////////////////////////////////////////////////
  static boolean Estdans(int sommet, int[] chemin, int n) {
    for (int i = 0 ; i <= n ; i++)
      if (chemin[i] == sommet)
        return true ;
    return false ;
  }
  
  static int Explorer(Graphe graphe, int sortie, int [] chemin, int n) {
    if (chemin[n] == sortie)
      return n ;
    for (int j = 0 ; j < graphe.nb_sommets ; j++)
      if (graphe.aretes[chemin[n]][j] && !Estdans(j, chemin, n)) {
        chemin[n + 1] = j ;
        int a = Explorer(graphe, sortie, chemin, n + 1) ;
        if (a != -1)
          return a ;
      }
    return -1 ;
  }

  // Programme principal
  // java labyrinthe_simple nom_fichier_du_graphe entree sortie
  /////////////////////////////////////////////////////////////
  public static void main(String [] args) {
    // Intialisation du graphique
    MacLib.InitQuickDraw() ;
    
    // Lecture d'un graphe
    Graphe graphe = new Graphe(args[0]) ;
    Afficher_Graphe(graphe) ;

    // Recherche du chemin
    int [] chemin = new int [graphe.nb_sommets] ;
    chemin[0] = Integer.parseInt(args[1]) ;
    int longueur = Explorer(graphe, Integer.parseInt(args[2]), chemin, 0) ;

    // Affichage du chemin
    if (longueur == -1)
      System.out.println("Il n'y a pas de chemin !") ;
    else {
      System.out.print("Le chemin : ") ;
      for (int i = 0 ; i < longueur ; i++)
        System.out.print(chemin[i] + " ") ;
      System.out.println("") ;
      Afficher_Chemin(graphe, chemin, longueur) ;
    }
  }
}

This document was translated from L^AT_EX by H^EV^EA.