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

#define PROBABILITY0 0.64
#define PROBABILITY1 0.32

typedef struct _node {
   int size;
   struct _node *P;
} node;

typedef node **MFT;

char **genmesh ( int n )
{
   char **A; 
   int i, j;
   double x, probability;

   srand((unsigned int)time(NULL));
   probability = (rand() % 2) ? PROBABILITY1 : PROBABILITY0;
   printf("*** Blocking probability = %4.2lf\n", probability);
   A = (char **)malloc((n+1) * sizeof(char *));
   for (i=0; i<=n; ++i) A[i] = (char *)malloc(n * sizeof(char));
   for (j=0; j<n; ++j) A[0][j] = '1';
   for (i=1; i<=n; ++i) {
      for (j=0; j<n; ++j) {
         x = (double)rand() / (double)RAND_MAX;
         A[i][j] = (x <= probability) ? '0' : '1';
         printf("%c ", A[i][j]);
      }
      printf("\n");
   }

   return A;
}

void printmesh ( char **A, int n )
{
   int i, j;

   printf("    +-");
   for (j=0; j<n; ++j) printf("--");
   printf("+\n");
   for (i=0; i<=n; ++i) {
      printf("    | ");
      for (j=0; j<n; ++j) {
         switch (A[i][j]) {
            case '0': printf("X "); break;
            case '1': printf("  "); break;
            case '2': printf("~ "); break;
            default: printf("? ");
         }
      }
      printf("|\n");
   }
   printf("    +-");
   for (j=0; j<n; ++j) printf("--");
   printf("+\n");
}

MFT initsets ( int n )
{
   MFT T;
   int i, j;

   T = (node **)malloc((n+1) * sizeof(node *));
   for (i=0; i<=n; ++i) {
      T[i] = (node *)malloc(n * sizeof(node));
      for (j=0; j<n; ++j) {
         T[i][j].size = 1;
         T[i][j].P = NULL;
      }
   }
   return T;
}

node *findset ( MFT T, int i, int j )
{
   node *p;

   p = &(T[i][j]);
   while (p -> P) p = p -> P;
   return p;
}

void mergesets ( node *p, node *q )
{
   if (p -> size <= q -> size) {
      p -> P = q;
      q -> size += p -> size;
   } else {
      q -> P = p;
      p -> size += q -> size;
   }
}

void mergeregions ( char **A, int n, MFT T )
{
   int i, j;
   node *p, *q;

   for (i=0; i<=n; ++i) for (j=0; j<n; ++j) if (A[i][j] == '1') {
      if ((i > 0) && (A[i-1][j] == '1')) {
         p = findset(T,i-1,j);
         q = findset(T,i,j);
         if (p != q) mergesets(p,q);
      }
      if ((j > 0) && (A[i][j-1] == '1')) {
         p = findset(T,i,j-1);
         q = findset(T,i,j);
         if (p != q) mergesets(p,q);
      }
   }
}

void findreach ( char **A, int n, MFT T )
{
   node *p;
   int i, j;

   p = findset(T,0,0);
   for (i=0; i<=n; ++i) for (j=0; j<n; ++j) {
      if (findset(T,i,j) == p) A[i][j] = '2';
   }
}

int main ( int argc, char *argv[] )
{
   int n, j;
   char **A;
   MFT T;

   if (argc > 1) n = atoi(argv[1]); else scanf("%d", &n);
   printf("n = %d\n", n);

   A = genmesh(n);
   printf("\n+++ Input mesh\n");
   printmesh(A,n);

   T = initsets(n);

   mergeregions(A,n,T);

   for (j=0; j<n; ++j) {
      if (findset(T,0,0) == findset(T,n,j)) {
         printf("\n+++ Liquid can seep through the mesh\n");
         break;
      }
   }
   if (j == n) printf("\n+++ Liquid cannot seep through the mesh\n");

   findreach(A,n,T);
   printf("\n+++ Reachable cells in the mesh\n");
   printmesh(A,n);

   exit(0);
}