Trouver le point d'entrée et de sortie d'un labyrinthe .

Messages postés
2
Date d'inscription
mercredi 24 décembre 2014
Statut
Membre
Dernière intervention
24 décembre 2014
-
Bonjour,
je travaille sur un mini projet qui consiste à construire un labyrinthe vierge ,après à générer un labyrinthe , à trouver le point d'entrée et de sortie , énumérer tout les chemins qui existent entre ces deux points et en suite trouver le chemin le plus optimal parmi ces derniers ,je n'arrive pas à trouver le point d'entrée et de sortie , voici mon propre code , enfin le code qui consiste juste à générer un labyrinthe ... j'ai besoin de votre aide pour trouver l'entrée et la sortie :
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<time.h>
 

#define VIDE 0
#define MUR 1
#define MAX 61  // 30 * 2 + 1
#define CELL 900  // 30 * 30
void lab1(int lab[MAX][MAX]);
void generation(int index, int lab[MAX][MAX], int arriere_x[CELL], int arriere_y[CELL], int x, int y, int n,int m, int visitee);
void aff_lab1(int lab[MAX][MAX], int n ,int m);
int fermee(int lab[MAX][MAX], int x, int y);
 
int main(void)
{
    srand((unsigned)time(NULL));
 
    int n,m;
    int index = 0;
    printf("création d'un labyrinthe\n\n");
    printf("input  (0 ~ 30): ");
    scanf("%d", &n);
    printf("input  (0 ~ 30): ");
    scanf("%d",&m);
    printf("\n");
    int lab[MAX][MAX];
    int arriere_x[CELL];
    int arriere_y[CELL];
 
    lab1(lab);
 
    arriere_x[index] = 1;
    arriere_y[index] = 1;
 
    generation(index, lab, arriere_x, arriere_y, 1, 1, n,m, 1);
    aff_lab1(lab, n ,m);
 
    getch();
    return 0;
}
 
void lab1(int lab[MAX][MAX])
{int a , b;
     for( a = 0; a < MAX; a++)
     {
         for( b = 0; b < MAX; b++)
         {
             if(a % 2 == 0 || b % 2 == 0)
                 lab[a][b] = 1;
             else
                 lab[a][b] = VIDE;
         }
     }
}
 
void generation(int index, int lab[MAX][MAX], int arriere_x[CELL], int arriere_y[CELL], int x, int y, int n,int m, int visitee)
{
    if(visitee < n * m)
    {
        int voisine_valide = -1;
        int voisine_x[4];
        int voisine_y[4];
        int pas[4];
 
        int x_prochain;
        int y_prochain;
 
        if(x - 2 > 0 && fermee(lab, x - 2, y))  // nord
        {
            voisine_valide++;
            voisine_x[voisine_valide]=x - 2;
            voisine_y[voisine_valide]=y;
            pas[voisine_valide]=1;
        }
 
        if(y - 2 > 0 && fermee(lab, x, y - 2))  // ouest
        {
            voisine_valide++;
            voisine_x[voisine_valide]=x;
            voisine_y[voisine_valide]=y - 2;
            pas[voisine_valide]=2;
        }
 
        if(y + 2 < m * 2 + 1 && fermee(lab, x, y + 2))  // est
        {
            voisine_valide++;
            voisine_x[voisine_valide]=x;
            voisine_y[voisine_valide]=y + 2;
            pas[voisine_valide]=3;
 
        }
 
        if(x + 2 < n * 2 + 1 && fermee(lab, x + 2, y))  // sud
        {
            voisine_valide++;
            voisine_x[voisine_valide]=x+2;
            voisine_y[voisine_valide]=y;
            pas[voisine_valide]=4;
        }
 
        if(voisine_valide == -1)
        {
            // backtrack
            x_prochain = arriere_x[index];
            y_prochain = arriere_y[index];
            index--;
        }
 
        if(voisine_valide!=-1)
        {
            int randomization = voisine_valide + 1;
            int random = rand()%randomization;
            x_prochain = voisine_x[random];
            y_prochain = voisine_y[random];
            index++;
            arriere_x[index] = x_prochain;
            arriere_y[index] = y_prochain;
 
            int rpas = pas[random];
 
            if(rpas == 1)
                lab[x_prochain+1][y_prochain] = VIDE;
            else if(rpas == 2)
                lab[x_prochain][y_prochain + 1] = VIDE;
            else if(rpas == 3)
                lab[x_prochain][y_prochain - 1] = VIDE;
            else if(rpas == 4)
                lab[x_prochain - 1][y_prochain] = VIDE;
            visitee++;
        }
 
        generation(index, lab, arriere_x, arriere_y, x_prochain, y_prochain, n,m, visitee);
    }
}
 
void aff_lab1(int lab[MAX][MAX], int n, int m)
{int a,b;
     for(a = 0; a < n* 2 + 1; a++)
     {
         for( b = 0; b < m * 2 + 1; b++)
         {
             if(lab[a][b] == MUR)
             { if(a%2==0)
                 printf("_");
               else if (b%2==0)
               printf("|");
               }
             else
                 printf(" ");
         }
         printf("\n");
     }
}
 
int fermee(int lab[MAX][MAX], int x, int y)
{
    if(lab[x - 1][y]  == MUR
       && lab[x][y - 1] == MUR
       && lab[x][y + 1] == MUR
       && lab[x + 1][y] == MUR
    )
        return 1;
 
    return 0;
}
Afficher la suite 

2 réponses

Messages postés
14667
Date d'inscription
lundi 11 juillet 2005
Statut
Modérateur
Dernière intervention
21 novembre 2019
90
0
Merci
Hello,

J'ai rajouté les balises code dans ton message pour plus de lisiblité.
Plus d'infos ici
Commenter la réponse de BunoCS
Messages postés
2
Date d'inscription
mercredi 24 décembre 2014
Statut
Membre
Dernière intervention
24 décembre 2014
0
Merci
merci BunoCS
Commenter la réponse de kratos58