1ere Candidature Informatique (Groupe 5): Projet 3  Henry Ledoux

#include < iostream . h>
const int m_max = 50;
const int n_max = 50;
typedef bool MatrMN[m_max ] [ n_max ] ;
void l e c t u r e (MatrMN laby , int m, int n ) ;
int gauche (MatrMN laby , int m, int n ) ;
int d r o i t e (MatrMN laby , int m, int n ) ;
bool m e i l l e u r (MatrMN laby , int m, int n ) ;
/∗ Deux f o n c t i o n s , l ’ une s u i t l e mur de d r o i t e , l ’ autre l e mur de gauche
∗ C e l l e−c i s u i t l e mur de d r o i t e ∗/

int

d r o i t e (MatrMN laby , int m, int n)

{ // d i r , e n t i e r deà 1 4 contenant l a d i r e c t i o n , 0 vers l e bas , 1 vers l a gauche

// e t c … i numero de l a l i g n e , j numero de colonne . cpt compte l e nombre de pas
// parcourus
int d i r = 0 , i = 0 , j = 1 , cpt = 1;

do {

// S e r i e de t e s t d e s t i n e s a t e s t e r l a d i r e c t i o n a prendre
i f ( d i r == 0) // Dans l e cas d ’ un deplacement vers l e bas :

{

i f ( laby [ i ] [ j − 1] == 0)  // On v e r i f i e s i l e passage e s t
// l i b r e a d r o i t e
d i r = ( d i r + 3) % 4;  // Tourner d ’ un quart de tour
// vers l a d r o i t e r e v i e n t a
// tourner de 3/4 vers l a gauche
// ( car −1%4 = −1, nous voudrions

// 3)

else i f ( laby [ i + 1 ] [ j ] ! = 0 )  // Si l e passage e s t b l o q u e
// devant :
i f ( laby [ i ] [ j + 1] == 0)  // On v e r i f i e s ’ i l e s t
// l i b r e a d r o i t e
d i r = ( d i r + 1) % 4;  // e t on y tourne

else

d i r = ( d i r + 2) % 4;  // Sinon on f a i t demi
// tour .

}

else i f ( d i r == 1)  // Test du cas d ’ un deplacement vers l a d r o i t e .

{

i f ( laby [ i + 1 ] [ j ] == 0)
d i r = ( d i r + 3) % 4;
else i f ( laby [ i ] [ j + 1 ] ! = 0 )
i f ( laby [ i − 1 ] [ j ] == 0)
d i r = ( d i r + 1) % 4;

else

d i r = ( d i r + 2) % 4;

}

else i f ( d i r == 2)  // Cas d ’ un deplacement vers l e haut .

{

i f ( laby [ i ] [ j + 1] == 0)
d i r = ( d i r + 3) % 4;
else i f ( laby [ i − 1 ] [ j ] ! = 0 )

i f ( laby [ i ] [ j − 1] == 0)
d i r = ( d i r + 1) % 4;

else

d i r = ( d i r + 2) % 4;

}

else i f ( d i r == 3)  // Cas d ’ un deplacement vers l a d r o i t e ;

{

i f ( laby [ i − 1 ] [ j ] == 0)
d i r = ( d i r + 3) % 4;
else i f ( laby [ i ] [ j − 1 ] ! = 0 )
i f ( laby [ i + 1 ] [ j ] == 0)
d i r = ( d i r + 1) % 4;

else

d i r = ( d i r + 2) % 4;

}

cpt++;  // Compte l e nombre de pas f r a n c h i . Modifie l e s
// coordonees du " curseur " en f o n c t i o n de l a d i r e c t i o n
// c h o i s i e precedement .
switch ( d i r )

{

case 0 :
i ++;
break ;
case 1 :
j ++;
break ;
case 2 :
i −−;
break ;
case 3 :
j −−;
break ;

}

}

while ( i > 0 && j > 0 && i < n − 1 && j < m − 1 ) ;  // La b o u c l e s ’ execute
// t a n t que l ’ on
// n ’ a t t e i n t pas un bord .
return cpt ;

}

// Le p r i n c i p e e s t l e meme pour l a f o n c t i o n gauche , mais on procede dans l ’ autre sens

int

gauche (MatrMN laby , int m, int n)

{

int d i r = 0 , i = 0 , j = 1 , cpt = 1;

do {

i f ( d i r == 0)

{

i f ( laby [ i ] [ j + 1] == 0)  // On v e r i f i e s i on peut tourner
// a gauche
d i r = ( d i r + 1) % 4;
else i f ( laby [ i + 1 ] [ j ] ! = 0 )  // Si l e chemin e s t b l o q u e devant
i f ( laby [ i ] [ j − 1] == 0)  // On v e r i f i e s ’ i l e s t
// l i b r e a d r o i t e
d i r = ( d i r + 3) % 4;

else

d i r = ( d i r + 2) % 4;

}

else i f ( d i r == 1)

{

i f ( laby [ i − 1 ] [ j ] == 0)
d i r = ( d i r + 1) % 4;
else i f ( laby [ i ] [ j + 1 ] ! = 0 )
i f ( laby [ i + 1 ] [ j ] == 0)
d i r = ( d i r + 3) % 4;

else

d i r = ( d i r + 2) % 4;

}

else i f ( d i r == 2)

{

i f ( laby [ i ] [ j − 1] == 0)
d i r = ( d i r + 1) % 4;
else i f ( laby [ i − 1 ] [ j ] ! = 0 )
i f ( laby [ i ] [ j + 1] == 0)
d i r = ( d i r + 3) % 4;

else

d i r = ( d i r + 2) % 4;

}

else i f ( d i r == 3)

{

i f ( laby [ i + 1 ] [ j ] == 0)
d i r = ( d i r + 1) % 4;
else i f ( laby [ i ] [ j − 1 ] ! = 0 )
i f ( laby [ i − 1 ] [ j ] == 0)
d i r = ( d i r + 3) % 4;

else

d i r = ( d i r + 2) % 4;

}

cpt++;
switch ( d i r )

{

case 0 :
i ++;
break ;
case 1 :
j ++;
break ;
case 2 :
i −−;
break ;
case 3 :
j −−;
break ;

}

}

while ( i > 0 && j > 0 && i < n − 1 && j < m − 1 ) ;
return cpt ;

}

bool

m e i l l e u r (MatrMN laby , int m, int n)

{

// La f o n c t i o n m e i l l e u r renvoie v r a i s i l e chemin de d r o i t e e s t p l u s court .
return ( d r o i t e ( laby , m, n ) < gauche ( laby , m, n ) ) ;

}

// Simple f o n c t i o n d e s t i n e e a a f f i c h e r l a matrice a l ’ ecran .

void

l e c t u r e (MatrMN laby , int m, int n)

{

for ( int i = 0 ; i < m; i++)

{

for ( int j = 0 ; j < n ; j++)
cout << laby [ i ] [ j ] << " " ;
cout << endl ;

}

}

void

main ( )

{

const int m = 9 , n = 9;
int j ;
MatrMN laby = {

{ 1 , 0 , 1 , 1 , 1 , 1 , 1 , 1 , 1 } , { 1 , 0 , 1 , 1 , 1 , 1 , 1 , 1 , 1 } , { 1 , 0 , 0 , 0 , 0 , 0 , 1 , 1 , 1 } , { 1 , 0 , 1 , 0 , 1 , 1 , 1 , 1 , 1 } , { 1 , 0 , 1 , 0 , 0 , 0 , 1 , 1 , 1 } , { 1 , 1 , 1 , 0 , 1 , 0 , 0 , 0 , 0 } , { 1 , 1 , 1 , 0 , 1 , 0 , 1 , 1 , 1 } , { 1 , 1 , 1 , 0 , 0 , 0 , 1 , 1 , 1 } , { 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 }

} ;

l e c t u r e ( laby , m, n ) ;

cout << "Longueur du trajet en suivant le mur de gauche: " <<

gauche ( laby , m,

         n) << ", longueur en suivant le mur de droite: " <<

d r o i t e ( laby , m, n) << endl ;

cout << "Le chemin le plus court est celui parcouru en suivant le mur de " ;

i f ( m e i l l e u r ( laby , m, n ) )
cout << "droite" << endl ;

else

cout << "gauche" << endl ;

}