/* File: palude.c */ /* Time-stamp: "2001-04-30 15:38:09 calvanes" */ /* Scopo: esercizio significativo sulla ricorsione */ /* Data una matrice di 0 e 1 che rappresenta una palude, cerca un attraversamento e lo stampa se esiste. Variante in cui sono possibili movimenti solo in avanti, cioe` da <riga,colonna> a - <riga-1, colonna+1> (solo se la riga non e` la prima) - <riga, colonna+1> - <riga+1, colonna+1> (solo se la riga non e` l'ultima) */ #include <stdio.h> #define M 5 /* numero di righe, cioe` larghezza della palude */ #define N 6 /* numero di colonne, cioe` lunghezza della palude, coincide con la lunghezza di un cammino attraverso la palude */ /* Cerca un cammino a partire dalla posizione <i,j> della palude. Restituisce vero (1) se il cammino e` stato trovato, falso (0) altrimenti. */ int CercaCammino (int palude[M][N], /* la palude */ int i, int j, /* posizione corrente */ int cammino[N]); /* vettore dove mem. cammino tovato */ /* Cerca un cammino che porti dalla prima fino all'ultima colonna della palude. Restituisce vero (1) se il cammino e` stato trovato, falso (0) altrimenti. */ int EsploraPalude (int palude [M][N], /* la palude */ int cammino[N]); /* vettore dove mem. cammino tovato */ /* Stampa su video una palude evidenziando un cammino attraverso asterischi.*/ void StampaCammino (int palude [M][N], int cammino[N]); int main(void) { /* una palude senza cammini */ int palude[M][N] = {{1,0,0,1,0,0}, {0,1,0,0,0,0}, {0,0,1,1,0,0}, {1,1,0,0,0,0}, {1,1,1,0,1,1}}; /* una palude con un cammino */ /* int palude[M][N] = {{1,0,0,1,0,0}, {1,0,0,0,0,0}, {0,1,0,0,0,1}, {0,0,1,1,1,0}, {0,1,0,0,0,0}}; */ int cammino[N]; /* vettore dove memorizzare il cammino trovato */ /* ricerca del cammino */ if (EsploraPalude(palude, cammino)) StampaCammino(palude, cammino); else printf("Non ci sono cammini che attraversano la palude\n"); return 0; } int CercaCammino (int palude[M][N], /* la palude */ int i, int j, /* posizione corrente */ int cammino[N]) /* vettore dove mem. cammino tovato */ /* Cerca un cammino a partire dalla posizione <i,j> della palude. Restituisce vero (1) se il cammino e` stato trovato, falso (0) altrimenti. */ { int trovato = 0; /* variabile booleana che memorizza se il cammino e` stato trovato */ if (palude[i][j] == 1) { /* sono sulla terraferma */ cammino[j] = i; /* aggiorno la pos. corrente nel cammino da restituire */ if (j == N-1) /* sono arrivato dall'altra parte della palude */ trovato = 1; else { /* cerco un passaggio nella colonna j+1 */ if (i > 0) /* non sono sulla prima riga; provo la posizione <i-1,j+1> */ trovato = CercaCammino(palude, i-1, j+1, cammino); if (!trovato) /* provo la posizione <i,j+1> */ trovato = CercaCammino(palude, i, j+1, cammino); if (!trovato && i < M-1) /* non sono sull'ultima riga; provo la posizione <i+1,j+1> */ trovato = CercaCammino(palude, i+1, j+1, cammino); } } return trovato; } int EsploraPalude (int palude [M][N], /* la palude */ int cammino[N]) /* vettore dove mem. cammino tovato */ /* Cerca un cammino che porti dalla prima fino all'ultima colonna della palude. Restituisce vero (1) se il cammino e` stato trovato, falso (0) altrimenti. */ { int i; int trovato = 0; /* variabile booleana che memorizza se il cammino e` stato trovato */ /* prova a passare per gli elementi della prima colonna, fino a quando non e` stato trovato un cammino */ for (i = 0; i < M && !trovato; i++) trovato = CercaCammino(palude, i, 0, cammino); return trovato; } void StampaCammino (int palude [M][N], int cammino[N]) /* Stampa su video una palude evidenziando un cammino attraverso asterischi. */ { int i, j; for (i=0; i < N; i++) printf("%d ", cammino[i]); printf("\n\n"); printf("Cammino che attraversa la palude:\n"); for (i = 0; i < M; i++) { for (j = 0; j < N; j++) { printf("%d", palude[i][j]); /* stampa l'elemento della matrice */ if (i == cammino[j]) /* se il punto fa parte del cammino */ printf("*"); /* stampa '*' */ else /* altrimenti */ printf(" "); /* stampa uno spazio */ } printf("\n"); } }