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

#define MAXWT 9999

typedef struct {
   int rowidx;
   int colidx;
} pair;

typedef struct {
   int rowidx;
   int colidx;
   int weight;
   char type;
} wpair;

typedef struct {
   int m, n;
   int **H;
   int **V;
   pair **P;
} maze;

typedef int **path;

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

typedef node **MFT;

maze initmaze ( int m, int n )
{
   maze M;
   int i, j;

   M.m = m; M.n = n;

   M.H = (int **)malloc((m-1)*sizeof(int *));
   for (i=0; i<m-1; ++i) {
      M.H[i] = (int *)malloc(n * sizeof(int));
      for (j=0; j<n; ++j) M.H[i][j] = 1;
   }

   M.V = (int **)malloc(m * sizeof(int *));
   for (i=0; i<m; ++i) {
      M.V[i] = (int *)malloc((n-1) * sizeof(int));
      for (j=0; j<n-1; ++j) M.V[i][j] = 1;
   }

   M.P = (pair **)malloc(m * sizeof(pair *));
   for (i=0; i<m; ++i) {
      M.P[i] = (pair *)malloc(n * sizeof(pair));
      for (j=0; j<n; ++j) M.P[i][j] = (pair){-1.-1};
   }

   return M;
}

char prncell ( int t )
{
   if (t == 1) return 'x';
   if (t == 2) return 'S';
   if (t == 3) return 'T';
   return ' ';
}

void prnmaze ( maze M, int **path )
{
   int i, j;

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

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

   T = (node **)malloc(m * sizeof(node *));
   for (i=0; i<m; ++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 quicksort ( wpair *E, int n )
{
   int i, j, k, p;
   wpair t;

   if ((n == 0) || (n == 1)) return;
   p = E[0].weight;
   i = 0; j = 1; k = n-1;
   while (j <= k) {
      if (E[j].weight == p) ++j;
      else if (E[j].weight < p) {
         t = E[i]; E[i] = E[j]; E[j] = t; ++i; ++j;
      } else {
         t = E[j]; E[j] = E[k]; E[k] = t; --k;
      }
   }
   quicksort(E,i);
   quicksort(E+j,n-j);
}

void MSTmaze ( maze M )
{
   int m, n, i, j, k, l, s;
   wpair *E;
   MFT T;
   node *p, *q;

   m = M.m; n = M.n; s = 2*m*n-m-n;
   E = (wpair *)malloc(s * sizeof(wpair));
   k = 0;
   for (i=0; i<m-1; ++i) for (j=0; j<n; ++j) {
      E[k].rowidx = i;
      E[k].colidx = j;
      E[k].weight = rand() % MAXWT;
      E[k].type = 'H';
      ++k;
   }
   for (i=0; i<m; ++i) for (j=0; j<n-1; ++j) {
      E[k].rowidx = i;
      E[k].colidx = j;
      E[k].weight = rand() % MAXWT;
      E[k].type = 'V';
      ++k;
   }
   quicksort(E,s);

   /* printf("Quick sort done...\n");
   for (i=0; i<s; ++i) printf("%5d", E[i].weight);
   printf("\n"); */

   T = initsets(m,n);
   k = l = 0;
   while (k < m*n-1) {
      i = E[l].rowidx; j = E[l].colidx;
      p = findset(T,i,j);
      if (E[l].type == 'H') q = findset(T,i+1,j);
      else q = findset(T,i,j+1);
      if (p != q) {
         if (E[l].type == 'H') M.H[i][j] = 0; else M.V[i][j] = 0;
         mergesets(p,q);
         ++k;
      }
      ++l;
   }

   for (i=0; i<m; ++i) free(T[i]); free(T);
   free(E);
}

void DFS ( maze M, int i, int j, int **visited )
{
   int d, u, v, m, n, rec;

   visited[i][j] = 1;
   m = M.m; n = M.n;
   for (d=0; d<4; ++d) {
      switch (d) {
         case 0: u = i; v = j-1; break;
         case 1: u = i-1; v = j; break;
         case 2: u = i; v = j+1; break;
         case 3: u = i+1; v = j; break;
      }
      if ((u >= 0) && (u < m) && (v >= 0) && (v < n) && (visited[u][v] == 0)) {
         rec = 0;
         switch (d) {
            case 0: if (M.V[u][v] == 0) rec = 1; break;
            case 1: if (M.H[u][v] == 0) rec = 1; break;
            case 2: if (M.V[i][j] == 0) rec = 1; break;
            case 3: if (M.H[i][j] == 0) rec = 1; break;
         }
         if (rec) {
            M.P[u][v] = (pair){i,j};
            DFS(M, u, v, visited);
         }
      }
   }
}

void DFStree ( maze M )
{
   int **visited, i, j, m, n;

   m = M.m; n = M.n;
   visited = (int **)malloc(m * sizeof(int *));
   for (i=0; i<m; ++i) {
      visited[i] = (int *)malloc(n * sizeof(int));
      for (j=0; j<n; ++j) visited[i][j] = 0;
   }
   DFS(M,0,0,visited);
   for (i=0; i<m; ++i) free(visited[i]);
   free(visited);
}

path genpath ( maze M, int u, int v, int x, int y )
{
   int m, n, i, j;
   path p;
   pair t;

   m = M.m; n = M.n;
   p = (int **)malloc(m * sizeof(int *));
   for (i=0; i<m; ++i) {
      p[i] = (int *)malloc(n * sizeof(int));
      for (j=0; j<n; ++j) p[i][j] = 0;
   }

   t = (pair){u,v};
   while (t.rowidx >= 0) {
      p[t.rowidx][t.colidx] = 1;
      t = M.P[t.rowidx][t.colidx];
   }

   t = (pair){x,y};
   while (p[t.rowidx][t.colidx] == 0) {
      p[t.rowidx][t.colidx] = 1;
      t = M.P[t.rowidx][t.colidx];
   }

   t = M.P[t.rowidx][t.colidx];
   while (t.rowidx >= 0) {
      p[t.rowidx][t.colidx] = 0;
      t = M.P[t.rowidx][t.colidx];
   }

   return p;
}

int main ( int argc, char *argv[] )
{
   int m, n, u, v, x, y;
   maze M;
   path p;

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

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

   M = initmaze(m,n);
   printf("\n+++ Initial maze\n"); prnmaze(M,NULL);

   MSTmaze(M);
   printf("\n+++ Random maze generated\n"); prnmaze(M,NULL);

   DFStree(M);

   do {
      u = rand() % m; v = rand() % n;
      x = rand() % m; y = rand() % n;
   } while ((u == x) && (v == y));
   p = genpath(M, u, v, x, y);
   p[u][v] = 2; p[x][y] = 3;
   printf("\n+++ Path from S = (%d,%d) to T = (%d,%d)\n", u, v, x, y);
   prnmaze(M,p);

   for (u=0; u<m; ++u) {
      if (u != m-1) free(M.H[u]);
      free(M.V[u]);
      free(M.P[u]);
      free(p[u]);
   }
   free(M.H); free(M.V); free(M.P); free(p);

   exit(0);
}