// maze utility routines
//
// R. Perry, March 1991; updated Nov 2006, Jan 2016, Apr 2023
//
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "maze.h"

int debug = 0;
int solve = 0;

/* pseudo-random  0 <= r < n */

int irand( int n)
{
  return n*(rand()/(RAND_MAX+1.0));
}

/* shuffle an array */

void shuffle( int a[], int n)
{
  while( n > 1) {
    int i = irand(n);
    --n;
    int t = a[n]; a[n] = a[i]; a[i] = t;
  }
}

struct cell **maze_alloc( int m, int n)
{
  if( m < 1 || n < 1) return 0;

  /* get space for row pointers */

  struct cell **r = malloc( m * sizeof(struct cell *));

  if( r == 0) return 0;

  /* get space for cell data */

  r[0] = malloc( m * n * sizeof(struct cell));

  if( r[0] == 0) {
    free( r); /* avoid leak */
    return 0;
  }

  /* set remaining row pointers */

  for( int i = 1; i < m; ++i) r[i] = r[i-1] + n;

  return r;
}

void maze_init( struct cell **maze, int m, int n)
{
  /* set all walls closed, type NEITHER, path OFF */

  for( int i = 0; i < m; ++i) for( int j = 0; j < n; ++j) {
    maze[i][j].left = maze[i][j].down = CLOSED;
    maze[i][j].type = NEITHER;
    maze[i][j].path = OFF;
  }

  maze[0][0].left = OPEN; /* entrance */
}

int maze_read( struct cell **maze, int m, int n)
{
  int left, down;

  for( int i = 0; i < m; ++i) for( int j = 0; j < n; ++j) {
    if( scanf( "%d%d", &left, &down) != 2) return 0;
    maze[i][j].left = left; maze[i][j].down = down;;
  }

  return 1;
}

void maze_print_raw( struct cell **maze, int m, int n)
{
  printf( "%d %d\n", m, n);

  for( int i = 0; i < m; ++i)
  {
    for( int j = 0; j < n; ++j) printf( " %d %d ", maze[i][j].left, maze[i][j].down);
    putchar( '\n');
  }
}

void maze_print_X( struct cell **maze, int m, int n)
{
  char *XX = debug ? "++" : "XX";

  /* top wall */

  for( int j = 0; j < n; ++j) printf( "%s%s", XX, XX); 

  printf( "%s\n", XX);

  for( int i = 0; i < m; ++i)
  {
    for( int j = 0; j < n; ++j)
    {
      if( maze[i][j].left == CLOSED) printf( "%s", XX); else printf( "  ");

      if( debug) switch( maze[i][j].type) {
	case SPANTREE: printf( "S "); break;
	case FRONTIER: printf( "F "); break;
	case NEITHER:  printf( "  "); break;
      } else
        printf( "  ");
    }

    if( i == m-1) /* maze exit */
      printf( "  \n");
    else
      printf( "%s\n", XX);

    for( int j = 0; j < n; ++j) {
      printf( "%s", XX);
      if( maze[i][j].down == CLOSED) printf( "%s", XX); else printf( "  ");
    }

    printf( "%s\n", XX);
  }

  if( debug) putchar( '\n');
}