#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<limits.h>
#include<time.h>

/* unica costante, voglio 3 uni */
#define MAX1 3

/* dimensioni matrice */
int MX, MY;

/* set di caratteri  utilizzati per la stampa, non era  richiesto dal testo
 * ma permette un allineamento migliore con matrici di grandi dimensioni */

char distanze[]="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";

/* prototipi ad uso interno */
void stampamatrice(int *m);
int  minimo(int *m, int y, int x);
int ancorazeri(int *m);

int main(int argc, char **argv){
  int *M, *M1;
  int ii,jj;

  /* chiedo dimensioni matrice */
  printf("Inserire larghezza matrice: ");
  scanf("%d", &MX);
  printf("Inserire altezza matrice: ");
  scanf("%d", &MY);

  /* uso la calloc che non solo alloca ma azzera
   * l'array */
  M=calloc(MX*MY,sizeof(int));
  /* per M1 posso usare malloc */
  M1=malloc(MX*MY*sizeof(int)); 

  if(!M||!M1){
    fprintf(stderr, "Errore in fase di allocazione memoria");
    exit(EXIT_FAILURE); 
  }


  /* genero matrice di partenza */
  srand(time(NULL));
  for(ii=0;ii<MAX1;++ii)
    M[rand()%MY*MX+rand()%MX]=1;
  /* NOTA:  per gestire  matrici  bidimensionali  con allocazione  dinamica
   * occorre  ricordare che  non  posso accedervi  usando  A[y][x] ma  devo
   * calcolare la posizione di ciascun elemento con A[y*larghezza+x] */

  /* matrice di lavoro inizialmente uguale a M */
  memcpy(M1,M,MX*MY*sizeof(int));

  /* stampo matrice di partenza */
  printf("Matrice M\n");
  stampamatrice(M);
  printf("\n");

  do{
    for(ii=0;ii<MY;++ii)
      for(jj=0;jj<MX;++jj){
	/* se lo avevo gia' calcolato inutile ripetere */
	if(M1[ii*MX+jj])
	  continue;
	/* calcolo il valore */
	M1[ii*MX+jj]=minimo(M,ii,jj);
      }


    /* ricopio risultato */
    memcpy(M,M1,MX*MY*sizeof(int));

  }while(ancorazeri(M));

  /* stampo risultato */
  printf("Risultato\n");
  stampamatrice(M);
  printf("\n");

  exit(EXIT_SUCCESS);
}

/* restituisce il minimo di M nel vicinato di x,y +1 se almeno uno!=0 
 * altrimenti restituisce 0 */
int  minimo(int *m, int y, int x){
  int min=INT_MAX; /* valore sufficientemente alto da non poter essere il minimo */
  int i,j;

  for(i=y-1;i<=y+1;++i)
    for(j=x-1;j<=x+1;++j){
      /* controllo i bordi e se il vicino ha valore non nullo */
      if(j<0||j>=MX||i<0||i>=MY||!m[i*MX+j])
	continue; 
      if(m[i*MX+j]<min)
	min=m[i*MX+j];
    }
  /* controllo se ha trovato un minimo */
  if(min==INT_MAX) return 0;

  /* restituisco minimo dei non zero */
  return min+1;
}

void stampamatrice(int *m){
  int x,y;

  for(y=0;y<MY;++y){
    for(x=0;x<MX;++x)
      printf("%c", distanze[m[y*MX+x]]);
    printf("\n");
  }

}


/* cerco di capire se esistono ancora degli zeri in M */
int ancorazeri(int *m){
  int i;

  for(i=0;i<MX*MY;++i)
    if(!m[i]) return 1;
  return 0;
}