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

#define CLOSED 0
#define OPEN 1

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

node **initrooms ( int m, int n )
{
   node **R;
   int i, j;

   R = (node **)malloc(m * sizeof(node *));
   for (i=0; i<m; ++i) {
      R[i] = (node *)malloc(n * sizeof(node));
      for (j=0; j<n; ++j) {
         R[i][j].size = 1;
         R[i][j].parent = &(R[i][j]);
      }
   }
   return R;
}

char **inithorwalls ( int m, int n )
{
   int i, j;
   char **H;

   H = (char **)malloc((m-1) * sizeof(char *));
   for (i=0; i<=m-2; ++i) {
      H[i] = (char *)malloc(n * sizeof(char));
      for (j=0; j<n; ++j) H[i][j] = CLOSED;
   }
   return H;
}

char **initverwalls ( int m, int n )
{
   int i, j;
   char **V;

   V = (char **)malloc(m * sizeof(char *));
   for (i=0; i<m; ++i) {
      V[i] = (char *)malloc((n-1) * sizeof(char));
      for (j=0; j<=n-2; ++j) V[i][j] = CLOSED;
   }
   return V;
}

void printlabyrinth ( char **H, char **V, int m, int n )
{
   int i, j;

   printf("    +"); for (j=0; j<n; ++j) printf("---+"); printf("\n");
   for (i=0; i<m; ++i) {
      printf("    |");
      for (j=0; j<=n-2; ++j)
         printf("   %c", (V[i][j] == CLOSED) ? '|' : ' ');
      printf("   |\n");
      if (i != m-1) {
         printf("    ");
         for (j=0; j<n; ++j) printf("+%s", (H[i][j] == CLOSED) ? "---" : "   ");
         printf("+\n");
      }
   }
   printf("    +"); for (j=0; j<n; ++j) printf("---+"); printf("\n");
}

node *find ( node **R, int i, int j )
{
   node *x;

   x = &(R[i][j]);
   while (x -> parent != x) x = x -> parent;
   return x;
}

int merge ( node **R, node *x, node *y )
{
   if (x == y) return x -> size;
   if (x -> size >= y -> size) {
      y -> parent = x;
      x -> size += y -> size;
      return x -> size;
   } else {
      x -> parent = y;
      y -> size += x -> size;
      return y -> size;
   }
}

void buildlabyrinth ( node **R, char **H, char **V, int m, int n )
{
   int i1, i2, j1, j2, s, nmerge;
   node *x, *y;

   s = 1; nmerge = 0;
   while (s < m*n) {
      if (rand()%2) {   /* Break horizontal wall */
         i1 = rand() % (m-1); i2 = i1 + 1;
         j1 = j2 = rand() % n;
         if (H[i1][j1] == OPEN) continue;
         x = find(R,i1,j1); y = find(R,i2,j2);
         if (x == y) continue;
         H[i1][j1] = OPEN;
      } else {          /* Break vertical wall */
         j1 = rand() % (n-1); j2 = j1 + 1;
         i1 = i2 = rand() % m;
         if (V[i1][j1] == OPEN) continue;
         x = find(R,i1,j1); y = find(R,i2,j2);
         if (x == y) continue;
         V[i1][j1] = OPEN;
      }
      s = merge(R,x,y);
      ++nmerge;
      /* printf("\n+++ %d-th wall removed...\n", nmerge);
      printlabyrinth(H,V,m,n); */
   }
   printf("\n+++ Labyrinth created after %d wall removals\n", nmerge);
}

int main ( int argc, char *argv[] )
{
   int m, n;
   node **R;
   char **H, **V;

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

   srand((unsigned int)time(NULL));

   R = initrooms(m,n);
   H = inithorwalls(m,n);
   V = initverwalls(m,n);

   printf("\n+++ Initial labyrinth\n");
   printlabyrinth(H,V,m,n);

   buildlabyrinth(R,H,V,m,n);
   printf("\n+++ Final labyrinth\n");
   printlabyrinth(H,V,m,n);

   exit(0);
}