#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
FILE *fileInput, *fileOutput; /* puntatori ai file di input e di output */
char **labirinto; /* labirinto */
char **migliorSoluzione; /* percorso migliore per risolvere il labirinto */
const int possibiliMosse[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; /* mosse possibili (destra, sinistra, giù, su) */
int righe, colonne; /* numero di righe e di colonne del labirinto */
int mosse = 0; /* numero di mosse fatte */
int minorNumeroDiMosse; /* minor numero di mosse fatte per risolvere il labirinto */
int startx, starty; /* posizioni di partenza */
int finishx, finishy; /* posizioni finali */
bool flag = true; /* flag per il primo tragitto completo */
void risolvi(int xtmp, int ytmp); /* prototipo */
int main(void)
{
int i, j; /* contatori */
char nomeFile[50] = {0}; /* nome del file di testo */
/* apertura del file di input scelto dall'utente */
do
{
printf("Inserire il nome del file (es. \"labirinto.txt\"): "); scanf("%s", nomeFile);
fileInput = fopen(nomeFile, "r");
} while(fileInput == NULL);
/* apertura del file di output */
fileOutput = fopen("output.txt", "w");
/* input di righe, colonne, posizione iniziale e finale */
fscanf(fileInput, "%d%d%d%d%d%d", &righe, &colonne, &startx, &starty, &finishx, &finishy);
/* allocazione dinamica del labirinto */
labirinto = (char**) malloc(sizeof(char*) * righe);
migliorSoluzione = (char**) malloc(sizeof(char*) * righe);
for(i=0;i<righe;i++)
{
labirinto[i] = (char*) malloc(sizeof(char) * colonne + 1);
migliorSoluzione[i] = (char*) malloc(sizeof(char) * colonne + 1);
}
/* input del labirinto dal file di testo */
for(i=0;i<righe;i++)
fscanf(fileInput, "%s", labirinto[i]);
/* chiamata principale della funzione */
risolvi(startx, starty);
/* stampa finale su schermo e su file */
if(flag)
{
fprintf(fileOutput, "Impossibile risolvere il labirinto");
printf("Impossibile risolvere il labirinto"); }
else
{
fprintf(fileOutput, "%d\n", minorNumeroDiMosse);
printf("%d\n", minorNumeroDiMosse
);
for(i=0;i<righe;i++)
{
for(j=0;j<colonne;j++)
{
fprintf(fileOutput, "%c", migliorSoluzione[i][j]);
printf("%c", migliorSoluzione
[i
][j
]); }
fprintf(fileOutput, "\n");
}
}
/* deallocazione del labirinto */
for(i=0;i<righe;i++)
{
free(labirinto[i]);
free(migliorSoluzione[i]);
}
free(labirinto);
free(migliorSoluzione);
/* chiusura dei file */
fclose(fileInput);
fclose(fileOutput);
return 0;
}
void risolvi(int xtmp, int ytmp)
{
int i, j; /* contatori */
/* se la posizione è fuori dal labirinto ritorna */
if(xtmp < 0 || xtmp >= colonne || ytmp < 0 || ytmp >= righe)
return;
/* se le mosse fatte sono maggiori del minorNumeroDiMosse ritorna */
if(!flag)
if(mosse > minorNumeroDiMosse)
return;
/* se la posizione del labirinto è '.' sostituisci con '*' altrimenti ritorna */
if(labirinto[ytmp][xtmp] == '.')
labirinto[ytmp][xtmp] = '*';
else
return;
/* se raggiunge la fine del labirinto */
if(xtmp==finishx && ytmp==finishy)
{
if(flag || minorNumeroDiMosse > mosse)
{
minorNumeroDiMosse = mosse;
flag = false;
/* copia il percorso */
for(i=0;i<righe;i++)
for(j=0;j<colonne;j++)
migliorSoluzione[i][j] = labirinto[i][j];
labirinto[ytmp][xtmp] = '.';
return;
}
}
/* quattro spostamenti possibili */
for(i=0;i<4;i++)
{
mosse++; /* aumenta il numero di mosse */
/* nuova posizione con chiamata della funzione ricorsiva */
risolvi(xtmp + possibiliMosse[i][0], ytmp + possibiliMosse[i][1]);
mosse--; /* diminuisce il numero di mosse */
}
labirinto[ytmp][xtmp] = '.';
}
