Questo sito utilizza cookies, anche di terze parti, per mostrare pubblicità e servizi in linea con il tuo account. Leggi l'informativa sui cookies.
Username: Password: oppure
mazesolver - mazesolver.c

mazesolver.c

Caricato da: _mikele_
Scarica il programma completo

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <stdbool.h>
  4.  
  5.  
  6. FILE *fileInput, *fileOutput;                                        /* puntatori ai file di input e di output */
  7. char **labirinto;                                                    /* labirinto */
  8. char **migliorSoluzione;                                             /* percorso migliore per risolvere il labirinto */
  9. const int possibiliMosse[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; /* mosse possibili (destra, sinistra, giù, su) */
  10. int righe, colonne;                                                  /* numero di righe e di colonne del labirinto */
  11. int mosse = 0;                                                       /* numero di mosse fatte */
  12. int minorNumeroDiMosse;                                              /* minor numero di mosse fatte per risolvere il labirinto */
  13. int startx, starty;                                                  /* posizioni di partenza */
  14. int finishx, finishy;                                                /* posizioni finali */
  15. bool flag = true;                                                    /* flag per il primo tragitto completo */
  16.  
  17.  
  18. void risolvi(int xtmp, int ytmp);                                    /* prototipo */
  19.  
  20.  
  21. int main(void)
  22. {
  23.     int i, j;                /* contatori */
  24.     char nomeFile[50] = {0}; /* nome del file di testo */
  25.  
  26.     /* apertura del file di input scelto dall'utente */
  27.     do
  28.     {
  29.         printf("Inserire il nome del file (es. \"labirinto.txt\"): ");
  30.         scanf("%s", nomeFile);
  31.         fileInput = fopen(nomeFile, "r");
  32.     } while(fileInput == NULL);
  33.  
  34.     /* apertura del file di output */
  35.     fileOutput = fopen("output.txt", "w");
  36.  
  37.     /* input di righe, colonne, posizione iniziale e finale */
  38.     fscanf(fileInput, "%d%d%d%d%d%d", &righe, &colonne, &startx, &starty, &finishx, &finishy);
  39.  
  40.     /* allocazione dinamica del labirinto */
  41.     labirinto = (char**) malloc(sizeof(char*) * righe);
  42.     migliorSoluzione = (char**) malloc(sizeof(char*) * righe);
  43.     for(i=0;i<righe;i++)
  44.     {
  45.         labirinto[i] = (char*) malloc(sizeof(char) * colonne + 1);
  46.         migliorSoluzione[i] = (char*) malloc(sizeof(char) * colonne + 1);
  47.     }
  48.  
  49.     /* input del labirinto dal file di testo */
  50.     for(i=0;i<righe;i++)
  51.         fscanf(fileInput, "%s", labirinto[i]);
  52.  
  53.     /* chiamata principale della funzione */
  54.     risolvi(startx, starty);
  55.  
  56.     /* stampa finale su schermo e su file */
  57.     if(flag)
  58.     {
  59.         fprintf(fileOutput, "Impossibile risolvere il labirinto");
  60.         printf("Impossibile risolvere il labirinto");
  61.     }
  62.     else
  63.     {
  64.         fprintf(fileOutput, "%d\n", minorNumeroDiMosse);
  65.         printf("%d\n", minorNumeroDiMosse);
  66.  
  67.         for(i=0;i<righe;i++)
  68.         {
  69.             for(j=0;j<colonne;j++)
  70.             {
  71.                 fprintf(fileOutput, "%c", migliorSoluzione[i][j]);
  72.                 printf("%c", migliorSoluzione[i][j]);
  73.             }
  74.  
  75.             fprintf(fileOutput, "\n");
  76.             printf("\n");
  77.         }
  78.     }
  79.  
  80.     /* deallocazione del labirinto */
  81.     for(i=0;i<righe;i++)
  82.     {
  83.         free(labirinto[i]);
  84.         free(migliorSoluzione[i]);
  85.     }
  86.     free(labirinto);
  87.     free(migliorSoluzione);
  88.  
  89.     /* chiusura dei file */
  90.     fclose(fileInput);
  91.     fclose(fileOutput);
  92.  
  93.     return 0;
  94. }
  95.  
  96. void risolvi(int xtmp, int ytmp)
  97. {
  98.     int i, j; /* contatori */
  99.  
  100.     /* se la posizione è fuori dal labirinto ritorna */
  101.     if(xtmp < 0 || xtmp >= colonne || ytmp < 0 || ytmp >= righe)
  102.         return;
  103.  
  104.     /* se le mosse fatte sono maggiori del minorNumeroDiMosse ritorna */
  105.     if(!flag)
  106.         if(mosse > minorNumeroDiMosse)
  107.             return;
  108.  
  109.     /* se la posizione del labirinto è '.' sostituisci con '*' altrimenti ritorna */
  110.     if(labirinto[ytmp][xtmp] == '.')
  111.         labirinto[ytmp][xtmp] = '*';
  112.     else
  113.         return;
  114.  
  115.     /* se raggiunge la fine del labirinto */
  116.     if(xtmp==finishx && ytmp==finishy)
  117.     {
  118.         if(flag || minorNumeroDiMosse > mosse)
  119.         {
  120.             minorNumeroDiMosse = mosse;
  121.             flag = false;
  122.  
  123.             /* copia il percorso */
  124.             for(i=0;i<righe;i++)
  125.                 for(j=0;j<colonne;j++)
  126.                     migliorSoluzione[i][j] = labirinto[i][j];
  127.  
  128.             labirinto[ytmp][xtmp] = '.';
  129.             return;
  130.         }
  131.     }
  132.  
  133.     /* quattro spostamenti possibili */
  134.     for(i=0;i<4;i++)
  135.     {
  136.         mosse++; /* aumenta il numero di mosse */
  137.         /* nuova posizione con chiamata della funzione ricorsiva */
  138.         risolvi(xtmp + possibiliMosse[i][0], ytmp + possibiliMosse[i][1]);
  139.         mosse--; /* diminuisce il numero di mosse */
  140.     }
  141.  
  142.     labirinto[ytmp][xtmp] = '.';
  143. }