N4tty
26-10-2011, 13:28
Salve ragazzi, sto codando un programmino in c dove devo progettare un labirinto (matrice) con n righe, m colonne e tot % di muri. Un omino all'interno che cerca di uscire andando su, giu, destra e sinistra per le posizioni libere (non in diagonale)
Come un idiota ho scritto scritto e sono andato a controllare tutto dopo aver finito... Cmq, dopo aver risolto i problemini vari, il programma viene compilato ma dà segmentation fault sulla funzione searchExit.
Questo è il code, magari qualcuno di voi con un po' di pazienza e altruismo capisce lo sbaglio e mi corregge. Grazie in anticipo.
/*Progetto per Programmazione dei Calcolatori per il corso di laurea in informatica*/
//inclusione delle librerie standard per l'input, l'output, generazione numeri casuali, ...
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
//inclusione dei file contenenti i messaggi di risposta del programma
#include "message.h"
//definisco le funzioni randomize e random, rispettivamente per inizializzare il seme random e per prendere un numero compreso tra 0 e x-1
#define random(x) rand() % x
#define randomize srand(time(NULL))
//definisco la struttura nodo (passaggi dell'omino) contenente un array di due elementi con le coordinate e un puntatore ad una struttura dello stesso tipo (nodo)
//che conterrà le coordinate precedenti ed il puntatore al precedente passaggio e così via (struttura dati pila LIFO)
typedef struct etichetta {
//array di due elementi e puntatore a struttura dati nodo
int element[2];
struct etichetta *next;
} nodo;
//definizione della funzione head, che dato un puntatore a nodo in input, ritorna l'array con le coordinate attuali
int *head(nodo *l) {
return l->element;
}
//definizione della funzione tail, che dato un puntatore a nodo come input, ritorna il puntatore al nodo precedente
nodo *tail(nodo *l) {
return l->next;
}
//definizione della funzione empty, che data una lista, libera la memoria da essa allocata senza ritornare nulla
void empty(nodo *l) {
//se è l'ultimo elemento della lista lo libero ed esco dalla funzione
if(l->next == NULL) {
free(l);
return;
}
//chiamo ricorsivamente la funzione sul prossimo della lista, poi libero la memoria allocata
empty(tail(l));
free(l);
return;
}
//definizione della funzione mostraPercorso, che dato il labirinto ed il numero di righe e colonne, mostra il percorso "visuale"
void mostraLabirinto(int *labirinto, int numrighe, int numcolonne) {
//variabili indici
int i,j;
//passo tutto il labirinto e mostro solo ingresso, uscita, muri e passaggio dell'omino
for(i=0;i<numrighe;i++) {
for(j=0;j<numcolonne;j++) {
switch(labirinto[i*numcolonne+j]) {
case 0:
printf("||\t");
break;
case 1:
printf(" \t");
break;
case 2:
printf("|x|\t");
break;
case 3:
printf("U\t");
break;
case 8:
printf("|X|\t");
break;
case 9:
printf("I\t");
break;
}
}
printf("\n");
}
printf("\n");
}
//definizione della funzione push, che dato in input un puntatore a nodo e due interi contenenti le coordinate da inserire nella pila, ritorna un nuovo puntatore a nodo
//con le coordinate date in input e il puntatore che punta al nodo passato in input
nodo *push(nodo *l, int elemento1, int elemento2) {
//se la lista è vuota
if(l == NULL) {
//alloco memoria per la pila e inserisco solamente le coordinate e faccio puntare next a null
l = (nodo*) malloc(sizeof(nodo));
l->element[0] = elemento1;
l->element[1] = elemento2;
l->next = NULL;
//se la pila non è vuota
} else {
//creo un puntatore a nodo e alloco la memoria
nodo *niu = (nodo*) malloc(sizeof(nodo));
//copio il valore della lista attuale nel nuovo puntatore
//poi inserisco nella pila le coordinate del passo da effettuare e faccio puntare next al puntatore creato da poco, niu
niu->element[0] = l->element[0];
niu->element[1] = l->element[1];
niu->next = l->next;
l->element[0] = elemento1;
l->element[1] = elemento2;
l->next = niu;
}
//ritorna la pila
return l;
}
//definizione della funzione viewTail, che dato un puntatore a nodo come input, stampa tutti i passaggi percorsi dall'omino senza ritornare niente
void viewTail(nodo *l) {
//se la pila è vuota, ritorna void (finisce la funzione, non c'è nessuna coordinata/passo da stampare)
if(l == NULL)
return;
//stampa le coordinate della pila e richiama ricorsivamente la funzione con in input la coda della pila (passaggio precedente).
printf("(%d, %d)\n", l->element[0], l->element[1]);
viewTail(tail(l));
}
//definizione della funzinoe searchExit, che dato in input un puntatore a nodo, un puntatore al labirinto, il numero delle righe e delle colonne del labirinto (matrice),
//ritorna 0 se non ci sono posizioni liberi adiacenti, 1 se ci sono e muove il passo verso la posizione libera
int searchExit(nodo *l, int *labirinto, int numrighe, int numcolonne) {
//inizializzazioni variabili su, giu, sinistra e destra, le coordinate contenente le posizioni adiacenti all'omino
//inizializzazione variabili indici i e j, variabile intera contenente il numero random per la decisione del passo,
//e una matrice possibilita contenente le coordinate delle posizione adiacenti libere
int destra=l->element[1]+1;
int sinistra=l->element[1]-1;
int giu=l->element[0]+1;
int su=l->element[0]-1;
int i=0, j=0;
int random=4;
int **possibilita;
//allocazione memoria per la matrice
possibilita = (int**) malloc(4*sizeof(int*));
for(i=0;i<4;i++) {
possibilita[i] = (int*) malloc(2*sizeof(int));
}
//controllo che le coordinate con le posizione adiacenti non siano fuori range ( su e sinistra < 0 e giu e destra > numero righe e colonne)
if(giu >= numrighe)
giu=(numrighe-1);
if(su < 0)
su=0;
if(destra >= numcolonne)
destra=(numcolonne-1);
if(sinistra < 0)
sinistra=0;
//setto tutte le coordinate della matrice possibilita a -1
for(i=0;i<4;i++) {
for(j=0;j<2;j++) {
possibilita[i][j] = -1;
}
}
//verifico le coordinate adiacenti se sono libere o se sono uscite, se sono uscite le inserisco nella pila ed esco dalla funzione (ho svolto il compito),
//se sono libere le inserisco nella matrice possibilita
//i sarà l'indice della matrice possibilita
i = 0;
//se la posizione è l'uscita
if(labirinto[su*numcolonne+l->element[1]] == 3) {
//inserisco nella pila le coordinate e ritorno 1
l = push(l, su, l->element[1]);
return 1;
//se invece è una posizione libera
} else if(labirinto[su*numcolonne+l->element[1]] == 1) {
//inserisco nella matrice possibilita le coordinate della posizione, ed incremento l'indice i
possibilita[i][0] = su;
possibilita[i][1] = l->element[1];
i++;
}
if(labirinto[giu*numcolonne+l->element[1]] == 3) {
l = push(l, giu, l->element[1]);
return 1;
} else if(labirinto[giu*numcolonne+l->element[1]] == 1) {
possibilita[i][0] = giu;
possibilita[i][1] = l->element[1];
i++;
}
if(labirinto[l->element[0]*numcolonne+destra] == 3) {
l = push(l, l->element[0], destra);
return 1;
} else if(labirinto[l->element[0]*numcolonne+destra] == 1) {
possibilita[i][0] = l->element[0];
possibilita[i][1] = destra;
i++;
}
if(labirinto[l->element[0]*numcolonne+sinistra] == 3) {
l = push(l, l->element[0], sinistra);
return 1;
} else if(labirinto[l->element[0]*numcolonne+sinistra] == 1) {
possibilita[i][0] = l->element[0];
possibilita[i][1] = sinistra;
i++;
}
//se non sono stati trovati passaggi accessibili (l'indice i è ancora a 0)
if(i == 0) {
//disalloco la memoria per la matrice possibilita e ritorno 0
for(j=0;j<4;j++) {
free(possibilita[j]);
}
free(possibilita);
return 0;
}
//prendo il numero random tra 0 e i-1, è l'indice della riga della matrice possibilita,
//per il movimento vengono prese le coordinate con quell'indice all'interno di possibilita
randomize;
random = random(i);
//la posizione attuale la metto nel labirinto come 2 = posizione già percorsa, mentre setto a 8 = posizione attuale le coordinate della posizione su cui muoverò il passo
labirinto[l->element[0]*numcolonne+l->element[1]] = 2;
labirinto[possibilita[random][0]*numcolonne+possibilita[random][1]] = 8;
//effettuo il passo inserendo nella pila le coordinate della posizione scelta tra quelle libere a random
l = push(l, possibilita[random][0], possibilita[random][1]);
//disalloco la memoria per la matrice possibilità e ritorno 1
for(j=0;j<4;j++) {
free(possibilita[j]);
}
free(possibilita);
return 1;
}
//definisco lista come un puntatore a nodo
typedef nodo* lista;
//inizio funzione main, il programma non terminerà fino a quando l'omino non ha trovato l'uscita o l'utente avrà voluto smettere di provare a cercarla
int main(int argc, char **argv) {
//definisco le variabili da utilizzare nel programma
int i=0, j=0; //indici generali
int *labirinto; //matrice labirinto
int nRighe=0, nColonne=0, percentualeMuri=0; //righe, colonne e percentuale muri
int scelta=0, random=0; //interi per il numero random e per la scelta tra righe e colonne per la posizione di entrata dell'omino
int xEntrata=0, yEntrata=0, xUscita=0, yUscita=0; //coordinate di entrata e uscita
int finePassi=0, fineMura=0; //finepassi è falsa fino a quando ci sono posizioni libere e non uscite, finemura conterrà il numero di muri da mettere
char ritenta = 'y'; //variabile per ritentare in caso ci si trova in una posizione bloccata
int distanzaDalluscita=0, maxR=0, minR=0, maxC=0, minC=0; //variabile contenente la distanza dall'uscita rispetto le coordinate attuali
//inizializzo a null la variabile percorso, contenente appunto le coordinate del percorso dell'omino
lista percorso;
percorso = NULL;
//nel richiamare l'eseguibile, devono essere passati come parametri il numero di righe, colonne e la percentuale di muri nel labirinto
//controllo che ci siano 4 parametri
if(argc != 4) {
//se non sono 4 stampo come richiamare l'eseguibile ed esco
EXIT_HOWTOUSE;
return 0;
//se sono 4
} else {
//imposto il numero di righe e colonne e percentuale mura come impostate dall'utente
nRighe = atoi(argv[1]);
nColonne = atoi(argv[2]);
percentualeMuri = atoi(argv[3]);
//calcolo il numero di muri da inserire
fineMura = (((nRighe-2)*(nColonne-2))*percentualeMuri)/100;
//controllo che l'utonto non abbia inserito valori non numerici o 0 per righe o colonne o un parametro fuori range per la percentuale ( 0-100)
//se qualche parametro è sballato
if((!nRighe) || (!nColonne) || (percentualeMuri < 0) || (percentualeMuri > 100)) {
//stampo il messaggio di errore e di esempio utilizzo ed esco
printf("Numero righe inserite: %d\nNumero colonne inserite: %d\nPercentuale muri: %d\n", nRighe, nColonne, percentualeMuri);
EXIT_HOWTOUSE;
return 0;
//parametri passati quasi sicuramente corretti, inizia il programma
} else {
//alloco memoria per il labirinto a seconda dei parametri passati dall'utente
labirinto = (int*) malloc(nRighe*nColonne*sizeof(int));
//legenda labirinto:
//0 muro, 1 posizione libera, 2 posizionei già percorsa(il tragitto dell'omino),
//3 = uscita, 9 = entrata, 8 = posizione attuale
//i muri ricoprono il perimetro del labirinto, all'interno della matrice,quindi imposto i lati del labirinto a 0
//prima colonna e ultima a 0
for(i=0;i<nRighe;i++) {
labirinto[i*nColonne] = 0;
labirinto[i*nColonne+nColonne-1] = 0;
}
//prima riga e ultima a 0
for(i=0;i<nColonne;i++) {
labirinto[i] = 0;
labirinto[(nRighe-1)*nColonne+i] = 0;
}
//imposto tutto il labirinto interno(non le mura) a -1
for(i=1;i<(nRighe-1);i++) {
for(j=1;j<(nColonne-1);j++) {
labirinto[i*nColonne+j] = -1;
}
}
//inizializzo il seme per i numeri random
randomize;
//finchè non finiscono i muri da mettere
while(fineMura>0) {
//settaggio dei muri all'interno del labirinto in base alla percentuale passata come parametro di input
for(i=1;i<(nRighe-1);i++) {
for(j=1;j<(nColonne-1);j++) {
//se le mura da mettere sono finite esco dal ciclo
if(fineMura <= 0)
break;
//se la posizione che sto controllando è già un muro, continuo passando alla coordinata successiva
if(labirinto[i*nColonne+j] == 0)
continue;
//pesco il numero, se è maggiore della percentuale imposto la posizione a 0 (muro) e decremento il numero di mura rimanenti
random = random(100) + 1;
if(random < percentualeMuri) {
labirinto[i*nColonne+j] = 0;
fineMura--;
}
}
}
}
//una volta finito il numero di muri, trasformo tutti i -1 del labirinto, in 1 (posizioni libere)
for(i=1;i<(nRighe-1);i++) {
for(j=1;j<(nColonne-1);j++) {
if(labirinto[i*nColonne+j] == -1)
labirinto[i*nColonne+j] = 1;
}
}
//l'omino è su di un lato del labirinto, ma non sugli angoli
//calcolo della posizione dell'omino
randomize;
//scelta a caso: 0 l'omino è su una riga, 1 l'omino è su una colonna
scelta = random(2);
switch(scelta) {
//prima riga
case 0:
//coordinata x random e y = 0
xEntrata = random(nRighe);
yEntrata = 0;
//se x = 0 o x = numero delle righe -1, l'omino si troverebbe ad un angolo del labirinto,
//quindi rispettivamente nei casi vengono incrementate e decrementate di uno
if(xEntrata == 0)
xEntrata++;
if(xEntrata == (nRighe-1))
xEntrata--;
//setto l'intero a 9 in quelle coordinate (ingresso) ed esco
labirinto[xEntrata*nColonne] = 9;
break;
//prima colonna
case 1:
//coordinata x = 0 e y random
yEntrata = random(nColonne);
xEntrata = 0;
//stesso discorso, l'omino potrebbe trovarsi su un angolo, in tal caso incremento-decremento
if(yEntrata == 0)
yEntrata++;
if(yEntrata == (nColonne-1))
yEntrata--;
//setto l'intero a 9 in quelle coordinate del labirinto (ingresso) ed esco
labirinto[yEntrata] = 9;
break;
}
//calcolo uscita labirinto
randomize;
//scelgo un x ed un y random
xUscita = random(nRighe);
yUscita = random(nColonne);
//se l'uscita si trova ad un angolo, è iraggiungibile, quindi in tal caso incremento/decremento la x di 1
//caso angolo in alto a sinistra
if(xUscita == 0 && yUscita == 0)
xUscita++;
//caso angolo in alto a destra
if(xUscita == 0 && yUscita == (nColonne-1))
xUscita++;
//caso angolo in basso a sinistra
if(xUscita == (nRighe-1) && yUscita == 0)
xUscita++;
//caso angolo in basso a destra
if(xUscita == (nRighe-1) && yUscita == (nColonne-1))
xUscita++;
//setto l'intero a 3 in quelle coordinate calcolate random del labirinto (uscita)
labirinto[xUscita*nColonne+yUscita] = 3;
//finchè l'utente non ha deciso di rifiutare il continuamento e finepassi è a 1 (non è stata trovata l'uscita precedentemente)
do {
//rimetto finepassi a 0 in caso è già stato provato di trovare l'uscita
finePassi = 0;
//primo passo del percorso
percorso = NULL;
percorso = push(percorso, xEntrata, yEntrata);
//in caso abbia già provato a trovare l'uscita, ripristino il labirinto iniziale
for(i=0;i<nRighe;i++) {
for(j=0;j<nColonne;j++) {
if(labirinto[i*nColonne+j] == 2 || labirinto[i*nColonne+j] == 8)
labirinto[i*nColonne+j] = 1;
}
}
labirinto[xEntrata*nColonne+yEntrata] = 9;
//finchè non si trova l'uscita o non ci sono più mosse da effettuare
while((percorso->element[0] != xUscita || percorso->element[1] != yUscita) && (finePassi != 1)) {
//se non ci sono più movimenti
if(!searchExit(percorso, labirinto, nRighe, nColonne)) {
//stoppo il ciclo while e annuncio l'impossibilità di continuare
finePassi = 1;
NOPASS;
}
//calcolo la distanza dall'uscita
//calcolando il maggiore tra le coordinate attuali e le coordinate di uscita, sottraendo poi dal maggiore il minore, sia
//per x che per y, si avrà la distanza in passi "in linea d'aria"
if(percorso->element[0] > xUscita) {
maxR = percorso->element[0];
minR = xUscita;
} else {
minR = percorso->element[0];
maxR = xUscita;
}
if(percorso->element[1] > yUscita) {
maxC = percorso->element[1];
minC = yUscita;
} else {
minC = percorso->element[1];
maxC = yUscita;
}
//calcolo differenza righe + differenza colonne
distanzaDalluscita = (maxR - minR) + (maxC - minC);
//stampa labirinto a video
mostraLabirinto(labirinto, nRighe, nColonne);
//dichiara la distanza dall'uscita in passi, sleep di 4 secondi e poi pulisce lo schermo
printf("\nDistanza dall'uscita: %d\n\n", distanzaDalluscita);
sleep(4);
system("cls");
}
//se si è trovata l'uscita (finepassi viene settato a 1 quando non ci sono più movimenti possibili, altrimenti è 0,
//se in questo momento finepassi = 0 vuol dire che ci si trova nell'uscita)
if(!finePassi) {
//congratulazioni e mostra del percorso
YOUWON;
printf("Percorso effettuato:\n\n");
viewTail(percorso);
mostraLabirinto(labirinto, nRighe, nColonne);
//altrimenti si può ritentare...
} else {
//stampo il messaggio di fallimento, mostro il percorso effettuato e libero la memoria da esso allocata
//dopodichè chiedo all'utente se vuole ritentare
YOULOSE;
viewTail(percorso);
printf("\n\nSei arrivato %d passi lontano dall'uscita!\n\n", distanzaDalluscita);
mostraLabirinto(labirinto, nRighe, nColonne);
empty(percorso);
RITENTA;
scanf("%c", &ritenta);
}
} while(ritenta != 'n' && finePassi == 1);
}
//disalloco la memoria per il labirinto e finisco
free(labirinto);
return 1;
}
}
per quel qualcuno che volesse richiare il debug, metto il codice di message.h:
#define EXIT_HOWTOUSE printf("Parametri inseriti scorrettamente\n\nrichiamare l'eseguibile inserendo dopo il numero di righe, di colonne e la percentuale di muri in questo modo: $ eseguibile righe colonne percentualemuri\n\n")
#define NOPASS printf("Fine delle possibili mosse da parte dell'omino, non è stata trovata una via d'uscita!\n")
#define YOUWON printf("Congratulazioni, è stato trovato il passaggio che porta all'uscita del labirinto.\n\n")
#define YOULOSE printf("Peccato, l'omino non ha trovato la via d'uscita...\nEcco il suo percorso;\n\n")
#define RITENTA printf("Ritentare? (Y/n)")
Come un idiota ho scritto scritto e sono andato a controllare tutto dopo aver finito... Cmq, dopo aver risolto i problemini vari, il programma viene compilato ma dà segmentation fault sulla funzione searchExit.
Questo è il code, magari qualcuno di voi con un po' di pazienza e altruismo capisce lo sbaglio e mi corregge. Grazie in anticipo.
/*Progetto per Programmazione dei Calcolatori per il corso di laurea in informatica*/
//inclusione delle librerie standard per l'input, l'output, generazione numeri casuali, ...
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
//inclusione dei file contenenti i messaggi di risposta del programma
#include "message.h"
//definisco le funzioni randomize e random, rispettivamente per inizializzare il seme random e per prendere un numero compreso tra 0 e x-1
#define random(x) rand() % x
#define randomize srand(time(NULL))
//definisco la struttura nodo (passaggi dell'omino) contenente un array di due elementi con le coordinate e un puntatore ad una struttura dello stesso tipo (nodo)
//che conterrà le coordinate precedenti ed il puntatore al precedente passaggio e così via (struttura dati pila LIFO)
typedef struct etichetta {
//array di due elementi e puntatore a struttura dati nodo
int element[2];
struct etichetta *next;
} nodo;
//definizione della funzione head, che dato un puntatore a nodo in input, ritorna l'array con le coordinate attuali
int *head(nodo *l) {
return l->element;
}
//definizione della funzione tail, che dato un puntatore a nodo come input, ritorna il puntatore al nodo precedente
nodo *tail(nodo *l) {
return l->next;
}
//definizione della funzione empty, che data una lista, libera la memoria da essa allocata senza ritornare nulla
void empty(nodo *l) {
//se è l'ultimo elemento della lista lo libero ed esco dalla funzione
if(l->next == NULL) {
free(l);
return;
}
//chiamo ricorsivamente la funzione sul prossimo della lista, poi libero la memoria allocata
empty(tail(l));
free(l);
return;
}
//definizione della funzione mostraPercorso, che dato il labirinto ed il numero di righe e colonne, mostra il percorso "visuale"
void mostraLabirinto(int *labirinto, int numrighe, int numcolonne) {
//variabili indici
int i,j;
//passo tutto il labirinto e mostro solo ingresso, uscita, muri e passaggio dell'omino
for(i=0;i<numrighe;i++) {
for(j=0;j<numcolonne;j++) {
switch(labirinto[i*numcolonne+j]) {
case 0:
printf("||\t");
break;
case 1:
printf(" \t");
break;
case 2:
printf("|x|\t");
break;
case 3:
printf("U\t");
break;
case 8:
printf("|X|\t");
break;
case 9:
printf("I\t");
break;
}
}
printf("\n");
}
printf("\n");
}
//definizione della funzione push, che dato in input un puntatore a nodo e due interi contenenti le coordinate da inserire nella pila, ritorna un nuovo puntatore a nodo
//con le coordinate date in input e il puntatore che punta al nodo passato in input
nodo *push(nodo *l, int elemento1, int elemento2) {
//se la lista è vuota
if(l == NULL) {
//alloco memoria per la pila e inserisco solamente le coordinate e faccio puntare next a null
l = (nodo*) malloc(sizeof(nodo));
l->element[0] = elemento1;
l->element[1] = elemento2;
l->next = NULL;
//se la pila non è vuota
} else {
//creo un puntatore a nodo e alloco la memoria
nodo *niu = (nodo*) malloc(sizeof(nodo));
//copio il valore della lista attuale nel nuovo puntatore
//poi inserisco nella pila le coordinate del passo da effettuare e faccio puntare next al puntatore creato da poco, niu
niu->element[0] = l->element[0];
niu->element[1] = l->element[1];
niu->next = l->next;
l->element[0] = elemento1;
l->element[1] = elemento2;
l->next = niu;
}
//ritorna la pila
return l;
}
//definizione della funzione viewTail, che dato un puntatore a nodo come input, stampa tutti i passaggi percorsi dall'omino senza ritornare niente
void viewTail(nodo *l) {
//se la pila è vuota, ritorna void (finisce la funzione, non c'è nessuna coordinata/passo da stampare)
if(l == NULL)
return;
//stampa le coordinate della pila e richiama ricorsivamente la funzione con in input la coda della pila (passaggio precedente).
printf("(%d, %d)\n", l->element[0], l->element[1]);
viewTail(tail(l));
}
//definizione della funzinoe searchExit, che dato in input un puntatore a nodo, un puntatore al labirinto, il numero delle righe e delle colonne del labirinto (matrice),
//ritorna 0 se non ci sono posizioni liberi adiacenti, 1 se ci sono e muove il passo verso la posizione libera
int searchExit(nodo *l, int *labirinto, int numrighe, int numcolonne) {
//inizializzazioni variabili su, giu, sinistra e destra, le coordinate contenente le posizioni adiacenti all'omino
//inizializzazione variabili indici i e j, variabile intera contenente il numero random per la decisione del passo,
//e una matrice possibilita contenente le coordinate delle posizione adiacenti libere
int destra=l->element[1]+1;
int sinistra=l->element[1]-1;
int giu=l->element[0]+1;
int su=l->element[0]-1;
int i=0, j=0;
int random=4;
int **possibilita;
//allocazione memoria per la matrice
possibilita = (int**) malloc(4*sizeof(int*));
for(i=0;i<4;i++) {
possibilita[i] = (int*) malloc(2*sizeof(int));
}
//controllo che le coordinate con le posizione adiacenti non siano fuori range ( su e sinistra < 0 e giu e destra > numero righe e colonne)
if(giu >= numrighe)
giu=(numrighe-1);
if(su < 0)
su=0;
if(destra >= numcolonne)
destra=(numcolonne-1);
if(sinistra < 0)
sinistra=0;
//setto tutte le coordinate della matrice possibilita a -1
for(i=0;i<4;i++) {
for(j=0;j<2;j++) {
possibilita[i][j] = -1;
}
}
//verifico le coordinate adiacenti se sono libere o se sono uscite, se sono uscite le inserisco nella pila ed esco dalla funzione (ho svolto il compito),
//se sono libere le inserisco nella matrice possibilita
//i sarà l'indice della matrice possibilita
i = 0;
//se la posizione è l'uscita
if(labirinto[su*numcolonne+l->element[1]] == 3) {
//inserisco nella pila le coordinate e ritorno 1
l = push(l, su, l->element[1]);
return 1;
//se invece è una posizione libera
} else if(labirinto[su*numcolonne+l->element[1]] == 1) {
//inserisco nella matrice possibilita le coordinate della posizione, ed incremento l'indice i
possibilita[i][0] = su;
possibilita[i][1] = l->element[1];
i++;
}
if(labirinto[giu*numcolonne+l->element[1]] == 3) {
l = push(l, giu, l->element[1]);
return 1;
} else if(labirinto[giu*numcolonne+l->element[1]] == 1) {
possibilita[i][0] = giu;
possibilita[i][1] = l->element[1];
i++;
}
if(labirinto[l->element[0]*numcolonne+destra] == 3) {
l = push(l, l->element[0], destra);
return 1;
} else if(labirinto[l->element[0]*numcolonne+destra] == 1) {
possibilita[i][0] = l->element[0];
possibilita[i][1] = destra;
i++;
}
if(labirinto[l->element[0]*numcolonne+sinistra] == 3) {
l = push(l, l->element[0], sinistra);
return 1;
} else if(labirinto[l->element[0]*numcolonne+sinistra] == 1) {
possibilita[i][0] = l->element[0];
possibilita[i][1] = sinistra;
i++;
}
//se non sono stati trovati passaggi accessibili (l'indice i è ancora a 0)
if(i == 0) {
//disalloco la memoria per la matrice possibilita e ritorno 0
for(j=0;j<4;j++) {
free(possibilita[j]);
}
free(possibilita);
return 0;
}
//prendo il numero random tra 0 e i-1, è l'indice della riga della matrice possibilita,
//per il movimento vengono prese le coordinate con quell'indice all'interno di possibilita
randomize;
random = random(i);
//la posizione attuale la metto nel labirinto come 2 = posizione già percorsa, mentre setto a 8 = posizione attuale le coordinate della posizione su cui muoverò il passo
labirinto[l->element[0]*numcolonne+l->element[1]] = 2;
labirinto[possibilita[random][0]*numcolonne+possibilita[random][1]] = 8;
//effettuo il passo inserendo nella pila le coordinate della posizione scelta tra quelle libere a random
l = push(l, possibilita[random][0], possibilita[random][1]);
//disalloco la memoria per la matrice possibilità e ritorno 1
for(j=0;j<4;j++) {
free(possibilita[j]);
}
free(possibilita);
return 1;
}
//definisco lista come un puntatore a nodo
typedef nodo* lista;
//inizio funzione main, il programma non terminerà fino a quando l'omino non ha trovato l'uscita o l'utente avrà voluto smettere di provare a cercarla
int main(int argc, char **argv) {
//definisco le variabili da utilizzare nel programma
int i=0, j=0; //indici generali
int *labirinto; //matrice labirinto
int nRighe=0, nColonne=0, percentualeMuri=0; //righe, colonne e percentuale muri
int scelta=0, random=0; //interi per il numero random e per la scelta tra righe e colonne per la posizione di entrata dell'omino
int xEntrata=0, yEntrata=0, xUscita=0, yUscita=0; //coordinate di entrata e uscita
int finePassi=0, fineMura=0; //finepassi è falsa fino a quando ci sono posizioni libere e non uscite, finemura conterrà il numero di muri da mettere
char ritenta = 'y'; //variabile per ritentare in caso ci si trova in una posizione bloccata
int distanzaDalluscita=0, maxR=0, minR=0, maxC=0, minC=0; //variabile contenente la distanza dall'uscita rispetto le coordinate attuali
//inizializzo a null la variabile percorso, contenente appunto le coordinate del percorso dell'omino
lista percorso;
percorso = NULL;
//nel richiamare l'eseguibile, devono essere passati come parametri il numero di righe, colonne e la percentuale di muri nel labirinto
//controllo che ci siano 4 parametri
if(argc != 4) {
//se non sono 4 stampo come richiamare l'eseguibile ed esco
EXIT_HOWTOUSE;
return 0;
//se sono 4
} else {
//imposto il numero di righe e colonne e percentuale mura come impostate dall'utente
nRighe = atoi(argv[1]);
nColonne = atoi(argv[2]);
percentualeMuri = atoi(argv[3]);
//calcolo il numero di muri da inserire
fineMura = (((nRighe-2)*(nColonne-2))*percentualeMuri)/100;
//controllo che l'utonto non abbia inserito valori non numerici o 0 per righe o colonne o un parametro fuori range per la percentuale ( 0-100)
//se qualche parametro è sballato
if((!nRighe) || (!nColonne) || (percentualeMuri < 0) || (percentualeMuri > 100)) {
//stampo il messaggio di errore e di esempio utilizzo ed esco
printf("Numero righe inserite: %d\nNumero colonne inserite: %d\nPercentuale muri: %d\n", nRighe, nColonne, percentualeMuri);
EXIT_HOWTOUSE;
return 0;
//parametri passati quasi sicuramente corretti, inizia il programma
} else {
//alloco memoria per il labirinto a seconda dei parametri passati dall'utente
labirinto = (int*) malloc(nRighe*nColonne*sizeof(int));
//legenda labirinto:
//0 muro, 1 posizione libera, 2 posizionei già percorsa(il tragitto dell'omino),
//3 = uscita, 9 = entrata, 8 = posizione attuale
//i muri ricoprono il perimetro del labirinto, all'interno della matrice,quindi imposto i lati del labirinto a 0
//prima colonna e ultima a 0
for(i=0;i<nRighe;i++) {
labirinto[i*nColonne] = 0;
labirinto[i*nColonne+nColonne-1] = 0;
}
//prima riga e ultima a 0
for(i=0;i<nColonne;i++) {
labirinto[i] = 0;
labirinto[(nRighe-1)*nColonne+i] = 0;
}
//imposto tutto il labirinto interno(non le mura) a -1
for(i=1;i<(nRighe-1);i++) {
for(j=1;j<(nColonne-1);j++) {
labirinto[i*nColonne+j] = -1;
}
}
//inizializzo il seme per i numeri random
randomize;
//finchè non finiscono i muri da mettere
while(fineMura>0) {
//settaggio dei muri all'interno del labirinto in base alla percentuale passata come parametro di input
for(i=1;i<(nRighe-1);i++) {
for(j=1;j<(nColonne-1);j++) {
//se le mura da mettere sono finite esco dal ciclo
if(fineMura <= 0)
break;
//se la posizione che sto controllando è già un muro, continuo passando alla coordinata successiva
if(labirinto[i*nColonne+j] == 0)
continue;
//pesco il numero, se è maggiore della percentuale imposto la posizione a 0 (muro) e decremento il numero di mura rimanenti
random = random(100) + 1;
if(random < percentualeMuri) {
labirinto[i*nColonne+j] = 0;
fineMura--;
}
}
}
}
//una volta finito il numero di muri, trasformo tutti i -1 del labirinto, in 1 (posizioni libere)
for(i=1;i<(nRighe-1);i++) {
for(j=1;j<(nColonne-1);j++) {
if(labirinto[i*nColonne+j] == -1)
labirinto[i*nColonne+j] = 1;
}
}
//l'omino è su di un lato del labirinto, ma non sugli angoli
//calcolo della posizione dell'omino
randomize;
//scelta a caso: 0 l'omino è su una riga, 1 l'omino è su una colonna
scelta = random(2);
switch(scelta) {
//prima riga
case 0:
//coordinata x random e y = 0
xEntrata = random(nRighe);
yEntrata = 0;
//se x = 0 o x = numero delle righe -1, l'omino si troverebbe ad un angolo del labirinto,
//quindi rispettivamente nei casi vengono incrementate e decrementate di uno
if(xEntrata == 0)
xEntrata++;
if(xEntrata == (nRighe-1))
xEntrata--;
//setto l'intero a 9 in quelle coordinate (ingresso) ed esco
labirinto[xEntrata*nColonne] = 9;
break;
//prima colonna
case 1:
//coordinata x = 0 e y random
yEntrata = random(nColonne);
xEntrata = 0;
//stesso discorso, l'omino potrebbe trovarsi su un angolo, in tal caso incremento-decremento
if(yEntrata == 0)
yEntrata++;
if(yEntrata == (nColonne-1))
yEntrata--;
//setto l'intero a 9 in quelle coordinate del labirinto (ingresso) ed esco
labirinto[yEntrata] = 9;
break;
}
//calcolo uscita labirinto
randomize;
//scelgo un x ed un y random
xUscita = random(nRighe);
yUscita = random(nColonne);
//se l'uscita si trova ad un angolo, è iraggiungibile, quindi in tal caso incremento/decremento la x di 1
//caso angolo in alto a sinistra
if(xUscita == 0 && yUscita == 0)
xUscita++;
//caso angolo in alto a destra
if(xUscita == 0 && yUscita == (nColonne-1))
xUscita++;
//caso angolo in basso a sinistra
if(xUscita == (nRighe-1) && yUscita == 0)
xUscita++;
//caso angolo in basso a destra
if(xUscita == (nRighe-1) && yUscita == (nColonne-1))
xUscita++;
//setto l'intero a 3 in quelle coordinate calcolate random del labirinto (uscita)
labirinto[xUscita*nColonne+yUscita] = 3;
//finchè l'utente non ha deciso di rifiutare il continuamento e finepassi è a 1 (non è stata trovata l'uscita precedentemente)
do {
//rimetto finepassi a 0 in caso è già stato provato di trovare l'uscita
finePassi = 0;
//primo passo del percorso
percorso = NULL;
percorso = push(percorso, xEntrata, yEntrata);
//in caso abbia già provato a trovare l'uscita, ripristino il labirinto iniziale
for(i=0;i<nRighe;i++) {
for(j=0;j<nColonne;j++) {
if(labirinto[i*nColonne+j] == 2 || labirinto[i*nColonne+j] == 8)
labirinto[i*nColonne+j] = 1;
}
}
labirinto[xEntrata*nColonne+yEntrata] = 9;
//finchè non si trova l'uscita o non ci sono più mosse da effettuare
while((percorso->element[0] != xUscita || percorso->element[1] != yUscita) && (finePassi != 1)) {
//se non ci sono più movimenti
if(!searchExit(percorso, labirinto, nRighe, nColonne)) {
//stoppo il ciclo while e annuncio l'impossibilità di continuare
finePassi = 1;
NOPASS;
}
//calcolo la distanza dall'uscita
//calcolando il maggiore tra le coordinate attuali e le coordinate di uscita, sottraendo poi dal maggiore il minore, sia
//per x che per y, si avrà la distanza in passi "in linea d'aria"
if(percorso->element[0] > xUscita) {
maxR = percorso->element[0];
minR = xUscita;
} else {
minR = percorso->element[0];
maxR = xUscita;
}
if(percorso->element[1] > yUscita) {
maxC = percorso->element[1];
minC = yUscita;
} else {
minC = percorso->element[1];
maxC = yUscita;
}
//calcolo differenza righe + differenza colonne
distanzaDalluscita = (maxR - minR) + (maxC - minC);
//stampa labirinto a video
mostraLabirinto(labirinto, nRighe, nColonne);
//dichiara la distanza dall'uscita in passi, sleep di 4 secondi e poi pulisce lo schermo
printf("\nDistanza dall'uscita: %d\n\n", distanzaDalluscita);
sleep(4);
system("cls");
}
//se si è trovata l'uscita (finepassi viene settato a 1 quando non ci sono più movimenti possibili, altrimenti è 0,
//se in questo momento finepassi = 0 vuol dire che ci si trova nell'uscita)
if(!finePassi) {
//congratulazioni e mostra del percorso
YOUWON;
printf("Percorso effettuato:\n\n");
viewTail(percorso);
mostraLabirinto(labirinto, nRighe, nColonne);
//altrimenti si può ritentare...
} else {
//stampo il messaggio di fallimento, mostro il percorso effettuato e libero la memoria da esso allocata
//dopodichè chiedo all'utente se vuole ritentare
YOULOSE;
viewTail(percorso);
printf("\n\nSei arrivato %d passi lontano dall'uscita!\n\n", distanzaDalluscita);
mostraLabirinto(labirinto, nRighe, nColonne);
empty(percorso);
RITENTA;
scanf("%c", &ritenta);
}
} while(ritenta != 'n' && finePassi == 1);
}
//disalloco la memoria per il labirinto e finisco
free(labirinto);
return 1;
}
}
per quel qualcuno che volesse richiare il debug, metto il codice di message.h:
#define EXIT_HOWTOUSE printf("Parametri inseriti scorrettamente\n\nrichiamare l'eseguibile inserendo dopo il numero di righe, di colonne e la percentuale di muri in questo modo: $ eseguibile righe colonne percentualemuri\n\n")
#define NOPASS printf("Fine delle possibili mosse da parte dell'omino, non è stata trovata una via d'uscita!\n")
#define YOUWON printf("Congratulazioni, è stato trovato il passaggio che porta all'uscita del labirinto.\n\n")
#define YOULOSE printf("Peccato, l'omino non ha trovato la via d'uscita...\nEcco il suo percorso;\n\n")
#define RITENTA printf("Ritentare? (Y/n)")