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

Signaler
Messages postés
2
Date d'inscription
mercredi 24 décembre 2014
Statut
Membre
Dernière intervention
24 décembre 2014
-
kratos58
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;
}

2 réponses

Messages postés
14744
Date d'inscription
lundi 11 juillet 2005
Statut
Modérateur
Dernière intervention
21 février 2020
91
Hello,

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

merci BunoCS