#include
#include
#include
#include
#define WIDTH 10
#define HEIGHT 5
#define UP 0
#define RIGHT 1
#define DOWN 2
#define LEFT 3
#ifdef TRUE
#undef TRUE
#endif /* TRUE */
#define TRUE 1

#define cell_empty(a) (!(a)->up && !(a)->right && !(a)->down && !(a)->left)
typedef struct {
    unsigned int up      : 1;
    unsigned int right   : 1;
    unsigned int down    : 1;
    unsigned int left    : 1;
    unsigned int path    : 1;
    unsigned int visited : 1;
} cell_t;
typedef cell_t *maze_t;

///functions prototype
void CreateMaze (maze_t maze, int width, int height);
void SolveMaze (maze_t maze, int width, int height);
void PrintMaze (maze_t maze, int width, int height);

int main ()
{
    clrscr();
    int width = WIDTH;
    int height = HEIGHT;
  maze_t maze;

  maze = (maze_t) calloc (width * height, sizeof (cell_t));
 
  CreateMaze (maze, width, height);
  PrintMaze (maze, width, height);

  (void) putchar ('\n');
  SolveMaze (maze, width, height);
  getch();
  PrintMaze (maze, width, height);
  getch();
  free (maze);
  exit (EXIT_SUCCESS);
  return (0);

}

void CreateMaze (maze_t maze, int width, int height)
{
  maze_t mp, maze_top;
    char paths [4];
    int visits, directions;

    visits = width * height - 1;
    mp = maze;
    maze_top = mp + (width * height) - 1;

  while (visits) {
 directions = 0;

 if ((mp - width) >= maze && cell_empty (mp - width))    //(1,0)
   paths [directions++] = UP; //0
 if (mp < maze_top && ((mp - maze + 1) % width) && cell_empty (mp + 1))//(0,1)
   paths [directions++] = RIGHT;   //1
 if ((mp + width) <= maze_top && cell_empty (mp + width)) //(1,0)
   paths [directions++] = DOWN; //2
 if (mp > maze && ((mp - maze) % width) && cell_empty (mp - 1)) //(0,1)
   paths [directions++] = LEFT;  //3

 if (directions) {
     visits--;
     directions = ((unsigned) rand () % directions);

   switch (paths [directions]) {
  case UP:
      mp->up = TRUE;
      (mp -= width)->down = TRUE;
      break;
  case RIGHT:
      mp->right = TRUE;
      (++mp)->left = TRUE;
      break;
  case DOWN:
      mp->down = TRUE;
      (mp += width)->up = TRUE;
      break;
  case LEFT:
      mp->left = TRUE;
    (--mp)->right = TRUE;
      break;
  default:
      break;
     }
 } else {
     do {
  if (++mp > maze_top)
      mp = maze;
     } while (cell_empty (mp));
 }
    }
}/* CreateMaze */

void SolveMaze (maze_t maze, int width, int height)
{
    maze_t *stack, mp = maze;
    int sp = 0;

    stack = (maze_t *) calloc (width * height, sizeof (maze_t));

  
    (stack [sp++] = mp)->visited = TRUE;

    while (mp != (maze + (width * height) - 1)) {

 if (mp->up && !(mp - width)->visited)
     stack [sp++] = mp - width;
 if (mp->right && !(mp + 1)->visited)
     stack [sp++] = mp + 1;
 if (mp->down && !(mp + width)->visited)
     stack [sp++] = mp + width;
 if (mp->left && !(mp - 1)->visited)
     stack [sp++] = mp - 1;

 if (stack [sp - 1] == mp)
     --sp;

 (mp = stack [sp - 1])->visited = TRUE;
    }
    while (sp--)
 if (stack [sp]->visited)
     stack [sp]->path = TRUE;

    free (stack);

}/* SolveMaze */

void PrintMaze (maze_t maze, int width, int height)
{
    int w, h;
    char *line, *lp;

    line = (char *) calloc ((width + 1) * 2, sizeof (char));
  
    maze->up = TRUE;
    (maze + (width * height) - 1)->down = TRUE;

    for (lp = line, w = 0; w < width; w++) {
 *lp++ = '1';
 if ((maze + w)->up)
     *lp++ = ((maze + w)->path) ? '0' : ' ';
 else
   *lp++ = '1';
    }
  *lp++ = '1';
  (void) puts (line);

    for (h = 0; h < height; h++) {
 for (lp = line, w = 0; w < width; w++) {
     if ((maze + w)->left)
  *lp++ = ((maze + w)->path && (maze + w - 1)->path) ? '0' : ' ';
     else
  *lp++ = '1';
     *lp++ = ((maze + w)->path) ? '0' : ' ';
 }
 *lp++ = '1';
 (void) puts (line);
 for (lp = line, w = 0; w < width; w++) {
   *lp++ = '1';
     if ((maze + w)->down)
  *lp++ = ((maze + w)->path && (h == height - 1 ||
    (maze + w + width)->path)) ? '0' : ' ';
     else

  *lp++ = '1';
 }
 *lp++ = '1';
 (void) puts (line);
 maze += width;
    }
    free (line);

}/* PrintMaze */