Salve a tutti,
Ultimamente ho provato a cimentarmi nella risoluzione di un esercizio sulla ricorsioneche riporto di seguito:
In un file è codificata una scacchiera sotto forma di matrice di caratteri NxM in cui il carattere ‘*’ rappresenta una barriera invalicabile mentre il carattere ‘#’ una pedina. Scrivere un programma C che determini se esiste almeno un cammino che permette alla pedina di raggiunge la cima della matrice:
La pedina si può muovere in qualunque posizione adiacente alla sua posizione attuale (8 possibili mosse)
123
4#5
678
Esempio di configurazione:
0000000000
0****00000
**00*00000
0000**0000
00000**000
000000*000
000000**00
00#00000**
000000000*
0000000000
in questo caso esiste almeno 1 percorso che permette alla pedina di raggiungere la cima della scacchiera.
Altro esempio:
0000000000
0****00000
**00*00000
0000**0000
00000**000
000000*000
000000***0
00#00000**
000000000*
0000000000
In questo caso non esiste nemmeno 1 percorso che permette alla pedina di raggiungere la cima della scacchiera.
Parte II
Si modifichi il programma in modo che restituisca la lunghezza del percorso più breve che permette alla pedina di raggiungere la cima della scacchiera. Eventualmente, si stampi la sequenza di coordinate che identifica tale percorso.
Non ho avuto alcun genere di problema nella risoluzione della prima parte,in cui ho usato una funzione ricorsiva in cui ho imposto al mio codice C di visitare la prima casella a '0' a partire da '#',mediante un ciclo for da -1 a 1,contrassegnare la casella visitata e ripetere(in modo ricorsivo) l'operazione a partire dalla nuova casella sino alla prima riga della matrice,in tal caso...printf("è stato trovato un percoso");
Quella che invece mi sta creando un significativo numero di è la seconda parte.
Qualcuno saprebbe propormi una soluzione??
è necessario usare uno Stack per l'aggiornamento delle lunghezze n dei percorsi?
Di seguito il codice relativo al programma svolto:
codice:
int visita(char** matr,int x, int y, int row, int col);
int main()
{
char** matr=NULL;
FILE* fp=NULL;
char str[MAX];
int res;
int col=0, row=0;
int i=0, j;
STACK s=NULL;
int num_mosse = 0;
s = STACK_init();
fp=fopen("matrice#.txt","r");
if(fgets(str,MAX,fp)==NULL) return -1;
col = strlen(str);
col--;
do{
matr = (char**) realloc(matr, (row+1)*sizeof(char*));
matr[row]=(char*) calloc(col, sizeof(char));
for(j=0;j<col;j++)
matr[row][j]=str[j];
row++;
}while(fgets(str,MAX,fp)!=NULL);
printf("\nla matrice ha questo contenuto");
for(i=0; i<row ; i++){
printf("\n");
for(j=0; j<col ;j++){
printf("%c",matr[i][j]);
}
}
for(i=0;i<row;i++){
for(j=0;j<col;j++){
if(matr[i][j]=='#'){
printf("\npunto di partenza: %d-%d ", i,j);
res = visita(matr,i,j,row,col);
if(res==1){
printf("\n ho trovato un percorso");
break;
}else{
if (res==0) printf("\n non ho trovato un percorso");
break;
}
}
}
}
for(i=0;i<row;i++){
printf("\n");
for(j=0;j<col;j++){
printf("%c",matr[i][j]);
if(matr[i][j]=='1')
matr[i][j]='0';
}
}
for(i=0;i<row;i++){
for(j=0;j<col;j++){
if(matr[i][j]=='#'){
res=visita_2( matr,i,j,row,col,s);
if(res ==1){
STACK_pop(s,&num_mosse);
printf("%d",num_mosse);
}
}
}
}
return 0;
}
int visita(char** matr,int x, int y, int row, int col){
int i = 0;
int j = 0;
int res;
if(x==0) return 1;
for(i=-1 ; i<=1 ; i++){
for(j=-1 ; j<=1 ; j++){
if(((x+i)<row && (x+i)>=0) && matr[x+i][y+j]=='0'){
matr[x+i][y+j]='1';
res = visita(matr,x+i, y+j, row, col);
if (res==1)
return 1;
}
}
}
return 0;
}
In attesa di avere risposte,
Saluti a tutti