[C] problema ricorsivo_ mappa asterischi e percorsi

[h1jack3r]

Ciao a tutti, mi sapete aiutare con questo problema?

Ho una mappa composta da asterischi e punti
ad esempio questa

..*...........*.....
..**...........*....
...****.........*...
.................*..
.........*..........
.........*..........
...**....*..........
.........*..........
..........*.........
...........****.....
....................
..........*.........


Voglio trovare la massima lunghezza che fanno gli asterischi adiacenti, in questo caso è 7, e poi alla fine stampare a video il pezzo di matrice contenente il percorso. Originariamente il problema era per matrici larbitrariamente lunghe, io lo sto risolvendo per quella specifica matrice per poi espanderlo al problema generico. La lunghezza non supera comunque i 20 caratteri. La matrice è in un file.

Per risolvere il problema avevo pensato ad una soluzione ricorsiva, quando trova il primo asterisco cerca nelle posizioni adiacenti se ce n'è un altro e va avanti. Solo che sono un po' niubbo con la ricorsione e trovo abbastanza difficoltà, mi dareste una mano?
Vi posto la parte di codice che ho già scritto...
Ho anche qualche dubbio sui puntatori da passare alla funzione

Ecco il programmino ovviamente ancora non funzionante



#include <stdio.h>
#include <conio.h>
#include <stdlib.h>

char **posiz;

char *trova_asterisco(char **mappa,int i, int j);



int main()
{

char mappa[20][21];
char mappa1[20];
FILE *fp;
char file[50];
int i,j;


//apertura del file
//printf("Inserire il nome del file della mappa\n");
//scanf("%s",file);
if((fp=fopen("mappa.txt","r"))==NULL){
printf("Impossibile aprire il file");
return 0;
}

//carico in memoria la matrice assumendo nota la dimensione
for(i=0;i<12;i++)
fgets(&mappa[i][0],80,fp);

for(i=0;i<12;i++){
for(j=0;j<20;j++){
printf("%c",mappa[i][j]);
}
printf("\n");
}


//trova primo asterisco
for(i=0;i<12;i++){
for(j=0;j<20;j++){
if(mappa[i][j]=='*')
{
printf("Primo asterisco in: %d, %d",i,j); //potrei salvare la posizione
//in variabili globali

//qui dovrei chiamare la procedura ricorsiva trova_asterisco
posiz=trova_asterisco(mappa,i,j);
getch();

return(0);
}
}

}

getch();
}



char *trova_asterisco(char **mappa,int i, int j)
{


if(mappa[i][j+1]=='*')
posiz=trova_asterisco(mappa,i,j);
else
if(mappa[i+1][j-1]=='*')
posiz=trova_asterisco(mappa,i,j);
else
if(mappa[i+1][j]=='*')
posiz=trova_asterisco(mappa,i,j);
else
if(mappa[i+1][j+1]=='*')
posiz=trova_asterisco(mappa,i,j);
else
return(&mappa[i][j]);


}

[h1jack3r]

Ah...aggiungo qualcosina,
Nella funzione ricorsiva non vado a tenere in conto le posizioni sopra alla mappa perchè scorrendole dall'alto dovrebbero essere già state visitate.
Informazione importante: non ci sono biforcazioni nei percorsi quindi quel problema è evitato.
Altro problema: credo ci voglia backtracking per poter testare tutti i percorsi ma non so come implementarlo.

[h1jack3r]

Ce l'ho praticamente fatta!
Questa versione non include il fatto che la matrice può essere grande a piacimento ma è studiata per funzionare a pennello su una matrice della dimensione di quella copiata prima. Il problema più grande è che dovrei stampare ora la parte di matrice contenente la sequenza più lunga e non so come fare, il mio programma ora come ora individua la sequenza più lunga ma non la stampa a video, devo trovare il modo (mi sa sempre con variabili globali) di memorizzare gli indici di partenza e arrivo della sequenza + lunga.

Ecco il codice se ci volete dare un'occhiata e darmi una mano.


/*versione 0.1
cerca tutte le sequenze di asterischi partendo dal primo asterisco
e stampa tute le sequenze
senza stampare la matrice come richiede nel problema
va trovato il modo di testare quale è + lunga
-->var globali lungh_max per la lunghezza
ci va una variabile che memorizzi anche le posizioni per poi stampare la
matrice alla fine
*/

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#define M 1000
char **posiz;
char **trova_asterisco(char **mappa,int i, int j);
char **malloc2d(int r, int c);
void trovamax();
int lunghezza_max[M];
int z=0;
int main()
{

char **mappa;//[20][21];
char mappa1[20];
FILE *fp;
char file[50];
int i,j;
for(i=0;i<1000;i++)
lunghezza_max[i]=0;

mappa=malloc2d(20,21);
//apertura del file
//printf("Inserire il nome del file della mappa\n");
//scanf("%s",file);
if((fp=fopen("mappa.txt","r"))==NULL){
printf("Impossibile aprire il file");
return 0;
}

//carico in memoria la matrice assumendo nota la dimensione
for(i=0;i<12;i++)
fgets(&mappa[i][0],80,fp);

for(i=0;i<12;i++){
for(j=0;j<20;j++){
printf("%c",mappa[i][j]);
}
printf("\n");
}



for(i=0;i<12;i++)
{
for(j=0;j<20;j++)
{
if(mappa[i][j]=='*')
{
printf("Primo asterisco in: %d, %d\n",i,j);
posiz=trova_asterisco(mappa,i,j);
printf("\n");
printf("La lunghezza massima finora trovata e':%d \n",lunghezza_max[z]);
//lunghezza_max[z]=0;
z++;
}
}
}
getch();
trovamax();



getch();
return(0);
}



char **trova_asterisco(char **mappa,int i, int j)
{

printf("%c",mappa[i][j]);
lunghezza_max[z]++;
if(mappa[i][j+1]=='*')
posiz=trova_asterisco(mappa,i,(j+1));
else
if(mappa[i+1][j-1]=='*')
posiz=trova_asterisco(mappa,(i+1),(j-1));
else
if(mappa[i+1][j]=='*')
posiz=trova_asterisco(mappa,(i+1),j);
else
if(mappa[i+1][j+1]=='*')
posiz=trova_asterisco(mappa,(i+1),(j+1));
else
return(&mappa[i][j]);

return(mappa);

}



char **malloc2d(int r, int c)
{
int i;
char **t=(char **)malloc(r*sizeof(char *));

for (i=0; i<r; i++)
t[i]=(char *)malloc(c*sizeof(char));


return t;
}


void trovamax()
{
int i;
int max=0;

for(i=0;i<M;i++)
if(lunghezza_max[i]>max)
max=lunghezza_max[i];

printf("La lunghezza massima trovata complesiva e': %d",max);
}

[h1jack3r]

Up!
idee?

[Fenomeno85]

Non ho ben capito quello che devi fare :D
~§~ Sempre E Solo Lei ~§~

[h1jack3r]

trovare la massima catena di asterischi e stampare il pezzo della matrice che li contiene.