Gli esercizi
Testi e soluzioni di alcuni esercizi
Percorso sulla matrice
/*
** percorso.c
**
** Leggere in input una matrice rettangolare A (100x10),
** composta da numeri 0 e 1. Verificare se esiste una sequenza
** di elementi di valore 1 adiacenti tali che si possa
** individuare un percorso sulla matrice dalla prima all'ultima
** riga, spostandosi sempre da un elemento di valore 1 ad un
** altro adiacente, senza mai tornare su righe gia' percorse
** in precedenza.
**
** Marco Liverani (liverani@mat.uniroma3.it) - Settembre 2001
*/
#include <stdlib.h>
#include <stdio.h>
#define RIGHE 8
#define COL 5
void leggi_matrice(int mat[RIGHE][COL]) {
int i, j;
for (i=0; i<RIGHE; i++)
for (j=0; j<COL; j++)
scanf("%d", &mat[i][j]);
return;
}
int percorso(int mat[RIGHE][COL], int i, int j) {
int risp;
if (mat[i][j] == 1) {
if (i==RIGHE-1) {
risp = 1;
} else {
if ((j>0 && percorso(mat, i+1, j-1)) || percorso(mat, i+1, j) || (j<COL-1 && percorso(mat, i+1, j+1)))
risp = 1;
else
risp = 0;
}
} else {
risp = 0;
}
return(risp);
}
int main(void) {
int M[RIGHE][COL], i;
leggi_matrice(M);
i=0;
while (i<COL && !percorso(M, 0, i))
i++;
if (i==COL)
printf("Il percorso NON esiste.\n");
else
printf("Il percorso esiste.\n");
return(0);
}