#include <omp.h>
#include <stdio.h>
#include <stdlib.h>

#define MIN(a,b) (((a)<(b))?(a):(b))
#define MAX(a,b) (((a)>(b))?(a):(b))



void find_comp( int m, int n, int a[m][n], int label[m][n] ) {
  int old_label[m][n];
  int change, itmax = 100*m*n;
  //
  for ( int i=0; i<m; i++ )
    for ( int j=0; j<n; j++ ) {
      old_label[i][j] = a[i][j]*(i*n+j+1);
      label[i][j] = 0;
    }
  //
  change = 1;
  while ( change ) {
    change = 0;
#pragma omp parallel for
    for ( int i=0; i<m; i++ ) {
      for ( int j=0; j<n; j++ ) {
	if ( a[i][j]==1 ) {
	  label[i][j]=old_label[i][j];
	  if ( j > 0 ) 
	    label[i][j] = MAX(label[i][j],old_label[i][j-1]);
	  if ( j < n-1 ) 
	    label[i][j] = MAX(label[i][j],old_label[i][j+1]);
	  if ( i > 0 ) 
	    label[i][j] = MAX(label[i][j],old_label[i-1][j]);
	  if ( i < m-1 ) 
	    label[i][j] = MAX(label[i][j],old_label[i+1][j]);
	  if ( label[i][j] != old_label[i][j] )
	    change = 1;
	}
      }
    }
    for ( int i=0; i<m; i++ )
      for ( int j=0; j<n; j++ )
	old_label[i][j]=label[i][j];
  }
}



void random_pix( int m, int n, int a[m][n] ) {
  for ( int i=0; i<m; i++ )
    for ( int j=0; j<n; j++ ) {
      if ( rand() > 3*(RAND_MAX/4) )
	a[i][j]=1;
      else
	a[i][j]=0;
    }
}
      




void write_pix_orig(int m, int n, int a[m][n]) {
  char c;
  for ( int i=0; i<m; i++ ) {
    for ( int j=0; j<n; j++ ) {
      c = (a[i][j]>0) ? 'X' : '.';
      printf("%c",c);
    }
    printf("\n");
  }
}

// Does not print unique label but gives some hint what the solution looks like...
void write_pix_comp( int m, int n, int label[m][n] ) {
  char c;
  int k;
  char labc[]=
"ABCDEFGHIJKLMNOPQRSTUVZYZabcdefghijklmnopqrstuvxyz1234567890";

  for ( int i=0; i<m; i++ ) {
    for ( int j=0; j<n; j++ ) {
      if ( label[i][j]==0 ) 
	c='.';
      else {
	k = label[i][j] % 60;
	c = labc[k];
      }
      printf("%c",c);
    }
    printf("\n");
  }
}

int main() {
  double t;
  int m, n;
  printf("Enter number of rows and columns in the random pixmap: ");
  scanf("%d %d",&m,&n);
  int a[m][n], label[m][n];
  random_pix( m, n, a );
  t = omp_get_wtime();
  find_comp( m, n, a, label );
  printf("\nElapsed time = %lf seconds.\n",omp_get_wtime()-t);

  if ( (m < 50) && (n < 80) ) {
    printf("\n");
    write_pix_orig( m, n, a );
    printf("\n");
    write_pix_comp( m, n, label );
  }
}