001: #include<stdio.h>
002: #include<stdlib.h>
003: #include<limits.h>
004: 
005: // prototipi funzioni
006: int evolvi(int n, int b[n][n]);
007: void stampa(int n, const int b[n][n]);
008: int max(int n, const int b[n][n]);
009: 
010: int main(int argc, char **argv){
011: 
012:   char f[1000];
013:   printf("File da aprire? ");
014:   scanf("%s", f);
015: 
016:   FILE *fp = fopen(f, "r");
017:   if(!fp)
018:   {
019:     perror("");
020:     exit(EXIT_FAILURE);
021:   }
022: 
023:   int n;
024:   fscanf(fp, "%d", &n); // leggo dimensione matrice
025: 
026:   int board[n][n];   // alloco dinamicamente usando VLA, qui lo posso fare visto che non ho eventuale necessita' di disallocare
027: 
028:   // imposto tutte le celle a 0 
029:   int r, c;
030:   for(r = 0; r < n; ++r)
031:     for(c = 0; c < n; ++c)
032:       board[r][c] = 0;
033: 
034: 
035:   while(fscanf(fp, "%d %d", &r, &c) == 2) // fino a che leggo coppie di numeri continuo
036:     board[r][c] = 1;
037: 
038:   fclose(fp);
039: 
040:   printf("Matrice in input:\n"); 
041:   stampa(n, board);
042: 
043:   int iter = 0;  //contatore iterazioni
044:   while(evolvi(n, board))
045:   {
046:     printf("\nCiclo %d:\n", ++iter); // incremento numero iterazione e lo stampo
047:     stampa(n, board);
048:   }
049: 
050:   printf("\nRisultato finale dopo %d iterazioni, il massimo valore ottenuto e' %d:\n", ++iter, max(n, board));
051:   stampa(n, board);
052: 
053:   return 0;
054: }
055: 
056: // restituisce il massimo valore contenuto nella matrice
057: int max(int n, const int b[n][n])
058: {
059:   int massimo = 0; // inizializzo con valore sufficientemente piccolo
060: 
061:   // ciclo su righe e colonne
062:   for(int r = 0; r < n; ++r)
063:     for(int c = 0; c < n; ++c)
064:       if(b[r][c] > massimo) // se trovo elemento maggiore di quanto trovato fino ad ora lo aggiorno
065:   massimo = b[r][c];
066: 
067:   return massimo;
068: }
069: 
070: // semplice stampa di matrice bidimensionale
071: void stampa(int n, const int b[n][n])
072: {
073:   for(int r = 0; r < n; ++r)
074:   {
075:     for(int c = 0; c < n; ++c)
076:     {
077:       printf("%3d", b[r][c]);
078:     }
079:     printf("\n\n");
080:   }
081: }
082: 
083: 
084: int evolvi(int n, int b[n][n])
085: {
086:   // tengo traccia se ho ancora o meno zeri
087:   int hoancorazeri = 0;
088: 
089:   // imposto una matrice temporanea in cui memorizzare
090:   // la versione aggiornata della matrice in ingresso alla funzione
091:   int tmp[n][n];
092: 
093:   // analizzo la matrice in ingresso cella per cella
094:   int r, c;
095:   for(r = 0; r < n; ++r)
096:     for(c = 0; c < n; ++c)
097:     {
098:       // se gia' elemento diverso da zero mi limito a copiarlo nella matrice temporanea
099:       if(b[r][c])
100:       {
101:   tmp[r][c] = b[r][c];
102:   continue; // inutile continuare con il ciclo
103:       }
104: 
105:       // se uguale a zero guardo i "vicini" ovvero tutte le celle che hanno coordinate +-1 della riga/colonna di quella attuale
106:       int minvalue = INT_MAX;  // variabile che mi serve per individuare il minimo valore tra i vicini, inizialmente la imposto ad un valore altissimo
107:       for(int vr = r-1; vr <= r+1; ++vr)
108:   for(int vc = c-1; vc <= c+1; ++vc)
109:   {
110:     // se sono al di fuori dei bordi della matrice devo ignorare
111:     if(vr < 0 || vr >= n || vc < 0 || vc >= n)
112:       continue;
113:     // se il vicino ha valore diverso da 0 e piu' piccolo di quelli incontrati aggiorno il valor minimo incontrato
114:     if(b[vr][vc] != 0  && b[vr][vc] < minvalue)
115:     {
116:       minvalue = b[vr][vc];
117:     }
118:   }
119:       // dopo aver esaminato il vicinato, se non ho aggiornato minvalue vuol dire che avevo solo zeri intorno alla cella di coordinate (r,c)
120:       if(minvalue == INT_MAX)
121:       {
122:   hoancorazeri = 1;
123:   tmp[r][c] = 0;
124:       }
125:       else // altrimenti aggiorno la cella
126:       {
127:   tmp[r][c] = minvalue + 1;
128:       }
129: 
130:     }
131: 
132:   // una volta calcolata l'evoluzione della matrice, la ricopio su quella che mi era stata passata
133:   for(r = 0; r < n; ++r)
134:     for(c = 0; c < n; ++c)
135:       b[r][c] = tmp[r][c];
136: 
137: 
138:   return hoancorazeri;
139: }
140: