codice:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define OK 1
#define KO -1
#define N 20
#define M 10
//prototipi funzioni
char** alloco_matrice ( char**, int*, int* );
void print_matrice ( char**, int );
int check_app ( int, int, int, int, int, int );
int percorso ( char**, int, int, int, int, int, int, int f[M][N] );
int dentro ( int x, int y, int nr, int nc );
/* MAIN */
int main ()
{
char** mat; //MATRICE DA ALLOCARE E COPIARE LA MAPPA
int f[M][N]; //MATRICE DI FLAG UTILIZZATA PER GESTIRE I MOVIMENTI SULLA MAPPA
int nr, nc;
int xS, yS;
int xA, yA;
int i, j;
mat = alloco_matrice ( mat, &nr, &nc );
for ( i=0; i<nr; i++ ) {
for ( j=0; j<nc; j++ ) {
f[i][j]=0;
}
}
print_matrice ( mat, nr );
printf ("Inserire coordinate partenza [x,y]: ");
scanf ("%d%d", &xS, &yS);
printf ("Inserire coordinate arrivo [x,y]: ");
scanf ("%d%d", &xA, &yA);
if ( check_app ( xS, yS, xA, yA, nr, nc ) == OK ) {
printf ("Coordinate corrette\n");
}
else {
printf ("Coordinate errate\n");
system("pause");
exit(1);
}
if ( percorso ( mat, xS, yS, xA, yA, nr, nc, f )== OK ) {
printf ("Percorso trovato\n");
}
else {
printf ("Percorso NON trovato\n");
}
system("pause");
return(1);
}
char** alloco_matrice ( char** m, int* nr, int* nc )
{
FILE *aptr;
char n_file[N], tmp[N];
int i;
printf ("Inserire nome file: ");
scanf ("%s", n_file);
aptr = fopen(n_file,"r");
if ( aptr == NULL ) {
printf ("Errore apertura file\n");
system("pause");
exit(1);
}
*nr=0;
while ( fscanf (aptr,"%s", tmp) != EOF ) {
(*nr)++;
}
m = (char**)malloc((*nr)*sizeof(char*));
*nc=strlen(tmp);
for ( i=0; i<(*nr); i++ ) {
m[i] = (char*)malloc( ((*nr)+1)*sizeof(char) );
}
i=0;
rewind(aptr);
while ( fscanf (aptr,"%s", m[i]) != EOF && i<(*nr) ) {
i++;
}
fclose(aptr);
return(m);
}
void print_matrice ( char** m, int nr )
{
int i;
for ( i=0; i<nr; i++ ) {
printf ("%s\n", m[i]);
}
}
/* FUNZIONE CONTROLLO INSERIMENTO COORDINATE CORRETTE */
int check_app ( int xS, int yS, int xA, int yA, int nr, int nc )
{
if ( (xS>=0) && (xS<nr && xS<nc ) ) {
if ( (yS>=0) && (yS<nr && yS<nc ) ) {
if ( (xA>=0) && (xA<nr && xA<nc ) ) {
if ( (yA>=0) && (yA<nr && yA<nc ) ) {
return(OK);
}
else return(KO);
}
else return (KO);
}
else return (KO);
}
else return (KO);
}
/* FUNZIONE RICORSIVA CHE CALCOLA IL PERCORSO */
int percorso ( char** m, int xS, int yS, int xA, int yA, int nr, int nc, int f[M][N] )
{
int x, y, i, j;
f[xS][yS] = 1;
for ( x=-1; x<=1; x++ ) { //CICLI PER MUOVERSI NELLE 8
for ( y=-1; y<=1; y++ ) { //CASELLE ADIACENTI AL PUNTO DI PARTENZA
if ( dentro ( xS+x, yS+y, nr, nc ) == OK ) {
if ( xS+x == xA && yS+y == yA ) {
return (OK);
}
else if ( m[xS+x][yS+y] == '.' && f[xS+x][yS+y] == 0 ) {
if ( percorso ( m, xS, yS, xA, yA, nr, nc, f ) == OK ) {
return(OK);
}
xS = xS + x;
yS = yS + y;
}
}
}
}
return (KO);
}
int dentro ( int x, int y, int nr, int nc )
{
if ( x<0 || x>=nr ) {
return (KO);
}
else if ( y<0 || y>=nc ) {
return (KO);
}
else {
return (OK);
}
}