codice:
#include<stdio.h>
#include<time.h>
#include"msg.h"
#include"const.h"
struct posizione {
int x;
int y;
struct posizione *pun;
};
struct posizione *testa=NULL;
struct uscita {
int x;
int y;
};
/* prototipi delle funzioni */
int empty(struct posizione *p);
struct uscita crea_uscita_labirinto(char **,int ,int );
struct posizione *crea_entrata_labirinto(char **matrice,int eu_lrig,int eu_lcol);
void visualizza_entrata(struct posizione *);
int exit1(struct posizione *p,struct uscita USC);
char **alloca_matrice(int ,int );
int righe_labirinto();
int colonne_labirinto();
int percentuale_muri_labirinto();
void muri_interni(char **,int ,int ,int);
int mostra_labirinto(char **,int ,int );
int scrivi_muro( char **,int ,int );
/* fine della dichiarazione dei prototipi delle funzioni */
int main()
{
struct posizione *P; // puntatore della lista
struct uscita ESCI;
char **L;//puntatore al labirinto
int N,M,K,conta=0;
N=righe_labirinto();
M=colonne_labirinto();
K=percentuale_muri_labirinto();
L=alloca_matrice(N,M);
conta=scrivi_muro(L,N,M);
muri_interni(L,K,N,M);
P = crea_entrata_labirinto(L,N,M);
ESCI=crea_uscita_labirinto(L,N,M);
while((!exit1(P,ESCI))&&(!empty(P)))
{
mostra_labirinto(L,N,M);
if(incrocio(P,L))
{
if(esplorato(P,L))
{
pop(P);
}
else
{
push(P);
}
avanza(P,L);
}
else if(vcieco(P,L))
{
top(P);
if(esplorato(P,L))
{
pop(P);
}
else
{
avanza(P,L);
}
}
else{ avanza(P,L);}}//chiusura while
if (empty(P))
{
printf("\tsono all'ingresso no uscita");
}
else printf("\tevviva ho trovato l'uscita");//chiusura else principale
system("PAUSE");
free(L);
return 0;
}
struct posizione *crea_entrata_labirinto(char **matrice,int eu_lrig,int eu_lcol)
{
struct posizione *coordinate_entrata, *punt;
int i,j,entrata=0;
srand(time(NULL));
coordinate_entrata = (struct posizione *)malloc(sizeof(struct posizione));
while(entrata==0)
{
i=rand()%eu_lrig;
if((i==0)||(i==eu_lrig-COSTANTE1))//serve per gli spigoli
{
j=rand()%eu_lcol;
if ((j!=0)&&(j!=eu_lcol-COSTANTE1))//serve per gli spigoli
{
matrice[i][j]=SIMBOLO_ENTRATA;
entrata=1;
}
}
else
{
j=rand()%eu_lcol;
if ((j==0)||(j==eu_lcol-1))//serve per gli spigoli
{
matrice[i][j]=SIMBOLO_ENTRATA;
entrata=1;
}
}
}
coordinate_entrata->x=i;
coordinate_entrata->y=j;
coordinate_entrata->pun = NULL;
return(coordinate_entrata);
}
void visualizza_entrata(struct posizione *p)
{
/* ciclo di scansione */
while(p != NULL)
{
printf("\tx=%d", p->x); // visualizza l'informazione
printf("\ty=%d", p->y); // visualizza l'informazione
p = p->pun; // scorre di un elemento
}
// printf("\nOK\n");
}
char **alloca_matrice(int all_righe,int all_colonne)
{
char **Labirinto;
int ii=0;
Labirinto=(char **)malloc(sizeof(char*)*all_righe);
for(ii=0;ii<all_righe;ii++)
{
Labirinto[ii]=(char *)malloc(sizeof(char)*all_colonne);
}
return (Labirinto);
}
int righe_labirinto()
{
int num=0;
printf("inserisci n:");
scanf("%d",&num);
return num;
}
int colonne_labirinto()
{
int num=0;
printf("inserisci m:");
scanf("%d",&num);
return num;
}
int percentuale_muri_labirinto()
{
int num=0;
printf("inserisci k:");
scanf("%d",&num);
return num;
}
int mostra_labirinto(char **matrice,int eu_lrig,int eu_lcol)
{
int i=0,j=0;
printf("\n");
for(i=0;i<eu_lrig;i++)
{
for(j=0;j<eu_lcol;j++)
{
printf("%c",matrice[i][j]);
}
printf("\n");
}
return 0;
}
int scrivi_muro( char **matrice,int sm_lrig,int sm_lcol)
{
int i,j,conta=0,muri=0;
for (i=0;i<sm_lrig;i++)
{
for (j=0;j<sm_lcol;j++)
{
if(((j!=0)&&(i!=0))&&((j!=sm_lcol-COSTANTE1)&&(i!=sm_lrig-COSTANTE1)))
{
matrice[i][j]=SIMBOLO_VUOTO;
}
else
{
matrice[i][j]=SIMBOLO_MURO;
}
conta++;
}
}
return conta;
}
void muri_interni(char **matrice,int kpercentuale,int mi_lrig,int mi_lcol)
{
srand(time(NULL));//serve per la random
int i,j,muri=0;
while((muri<kpercentuale)&&muri!=((mi_lcol-COSTANTE2)*(mi_lrig-COSTANTE2)))
{
i=rand()%mi_lrig;
j=rand()%mi_lcol;
if(((j!=0)&&(i!=0))&&((j!=mi_lcol-COSTANTE1)&&(i!=mi_lrig-COSTANTE1))&&matrice[i][j]!=SIMBOLO_MURO)
{
matrice[i][j]=SIMBOLO_MURO;
muri++;
}
}
// return 0;
}
struct uscita crea_uscita_labirinto(char **matrice,int eu_lrig,int eu_lcol)
{
int i,j,uscita=0;
struct uscita posizione;
while(uscita==0)
{
i=rand()%eu_lrig;
if ((i==0)||(i==eu_lrig-COSTANTE1)) //se si trova all'inizio o alla fine della riga
{
//bisogna mette un controllo per far si che l'entrata e l'uscita non combacino
j=rand()%eu_lcol;
if ((j==0)||(j==eu_lcol-COSTANTE1)) //serve per nn entrare negli spigoli :-)
{
}
else
{
posizione.x=i;
posizione.y=j;
matrice[i][j]=SIMBOLO_USCITA;
uscita=1;
}
}
else
{
j=rand()%eu_lcol;
posizione.x=i;
posizione.y=j;
matrice[i][j]=SIMBOLO_USCITA;
uscita=1;
}
return posizione;
}
}
int empty(struct posizione *p){
visualizza_entrata(p);
return p==NULL;
}
int esplorato(struct posizione *p,char **L){
printf("\t\t ESPLORATO\n");
visualizza_entrata(p);
int e,x,y;
x=p->x;
y=p->y;
e=VERO;
if((L[x-1][y]==SIMBOLO_VUOTO)||(L[x][y-1]==SIMBOLO_VUOTO)||(L[x+1][y]==SIMBOLO_VUOTO)||(L[x][y+1]==SIMBOLO_VUOTO))
{e=FALSO;}
return e;
}//fine esplorato
int vcieco(struct posizione *p,char **L){
int c,x,y;
x=p->x;
y=p->y;
c=FALSO;
if (((p->x)-1)>=0) {
if((L[x-1][y]!=SIMBOLO_VUOTO)&&(L[x][y-1]!=SIMBOLO_VUOTO)&&(L[x+1][y]!=SIMBOLO_VUOTO)&&(L[x][y+1]!=SIMBOLO_VUOTO))
{c=VERO;}}
return c;
}//fine esplorato
int exit1(struct posizione *p,struct uscita USC){
printf("\t\t USCITA\n");
int u,x,y,xu,yu;
u=FALSO;
if((p->x==USC.x)&&(p->y==USC.y)){u=VERO;}
return u;
}
int avanza(struct posizione *p,char **L){ //sicuro nn va
printf("\t\tAVANZA\n");
int x,y;
x=p->x;
y=p->y;
if((L[x+1][y]==SIMBOLO_VUOTO)||(L[x+1][y]==SIMBOLO_USCITA))
{x++;
}
else{
if((L[x][y+1]==SIMBOLO_VUOTO)||(L[x][y+1]==SIMBOLO_USCITA))
{y++;}
else{
if((L[x-1][y]==SIMBOLO_VUOTO)||(L[x-1][y]==SIMBOLO_USCITA))
{x--;}
else{
if((L[x][y-1]==SIMBOLO_VUOTO )||(L[x][y-1]==SIMBOLO_USCITA))
{y--;}
}
}
}
//devo scrivere i valori dentro al puntatore :D
p->x=x;
p->y=y;
L[x][y]=SIMBOLO_CAMMINO;
}
int pop(struct posizione *p){ //mamma mia
printf("\t\t POP\n");
struct posizione *temp;
temp=testa;
testa=p->pun;
free(temp);
}
int push(struct posizione *p){
printf("\t\t Push\n");
struct posizione *newp;
newp=(struct posizione *)malloc(sizeof(struct posizione));
if (newp!=NULL){
newp->x=p->x;
newp->y=p->y;
newp->pun=testa;
testa=newp;
}else{ return FALSO;}
visualizza_entrata(p);
}//mamma mia
int top(struct posizione *p){
printf("\t\t TOP\n");
p->pun=testa;
}
int incrocio(struct posizione *p,char **lab){
printf("\t\tINCROCIO\n");
int pi;
//x=p->x;
//y=p->y;
// printf("incrocio[%d][%d]",x,y);
visualizza_entrata(p);
pi=0;
if (((p->x)-1)>=0) {//bisogna mettere il controllo anche se è maggiore del massimo n e m
if((lab[(p->x)-1][p->y]==SIMBOLO_VUOTO)||(lab[(p->x)-1][p->y]==SIMBOLO_CAMMINO)){pi++;}
if((lab[p->x][p->y-1]==SIMBOLO_VUOTO)||(lab[p->x][p->y-1]==SIMBOLO_CAMMINO)){pi++;}
if((lab[(p->x)+1][p->y]==SIMBOLO_VUOTO)||(lab[(p->x)+1][p->y]==SIMBOLO_CAMMINO)){pi++;}
if((lab[p->x][p->y+1]==SIMBOLO_VUOTO)||(lab[p->x][p->y+1]==SIMBOLO_CAMMINO)){pi=pi++;}
}
// printf("i=%d - FINE INCROCIO",i);
//system("PAUSE");
return (pi>2);
}