미로 MAZE (데이터 구조)

#include <iostream.h>
#include <stdlib.h>
#include <string.h>
#define Edge 10
#define PLUS 5
#define STA_SIZE 100
#define Startx 1
#define Starty 1
typedef struct Datastore{
 int x, y, d, lsx, lsy;
 bool nl;
} Datastore, *Link; //       
Datastore InitDatastore (Datastore &d) {
 d.x = d.lsx = Startx;
 d.y = d.lsy = Starty;
 d.d = 4;
 d.nl = false;
 return d;
}
typedef struct {
 Link base;
 Link top;
 int stacksize;
 // count            
 int count;
 //  array                        
 bool array[Edge*Edge];
} SqStack; //  
bool Push(SqStack &S, Datastore &e)
{
 if(S.top - S.base >= S.stacksize) {
  S.base = (Link) realloc (S.base, (S.stacksize + PLUS) * sizeof (Datastore));
  if (!S.base) return false;
  S.top = S.base + S.stacksize;
  S.stacksize += PLUS;
 }
 *(++S.top) = e;
 S.count++;
 return true;
} // Push  
bool Pop(SqStack &S, Datastore &e) {
 if(S.top == S.base) return false;
 e = *(--S.top);
 S.count--;
 return true;
} // Pop  
bool InitStack (SqStack &S) {
 S.base = (Link) malloc (STA_SIZE * sizeof(Datastore));
 if(!S.base) return false;
 S.top = S.base;
 S.stacksize = STA_SIZE;
 S.count = 0;
 for(int i = 0; i<Edge*Edge; i++ )
  S.array[i] = false;
 return true;
} //      S
bool DestroyStack (SqStack &S) {
 if(!S.base) return false;
 for (int i = 0; i<STA_SIZE; i++)
  free(S.top);
 return true;
}
bool NextPos (int a[], SqStack &S, Datastore &e) {
 // case    ,              
 //          ,     ,    d=0  
 for(; e.d>=0; )
 {
  switch(e.d)
  {
  case 4:
   // right 
   //    1,        
   e.d--;
   //        (0)   (-1),     ,           ,                   
   //        ,   ,       
   if(a[S.top->x * Edge + (S.top->y + 1)] <= 0 && S.top->lsy != (e.y + 1) && S.array[S.top->x * Edge + (S.top->y + 1)] == false)
   {
    e.y++;
    S.array[S.top->x * Edge + (S.top->y + 1)] = true;
    return true;
   }
   break;
  case 3:
   // down
   e.d--;
   if(a[(S.top->x + 1) * Edge + S.top->y] <= 0 && S.top->lsx != (e.x + 1) && S.array[(S.top->x + 1) * Edge + S.top->y] == false)
   {
    e.x++;
    S.array[(S.top->x + 1) * Edge + S.top->y] = true;
    return true;
   }
   break;
  case 2:
   // left
   e.d--;
   if(a[S.top->x * Edge + (S.top->y - 1)] <= 0 && S.top->lsy != (e.y - 1) && S.array[S.top->x * Edge + (S.top->y - 1)] == false)
   {
    e.y--;
    S.array[S.top->x * Edge + (S.top->y - 1)] = true;
    return true;
   }
   break;
  case 1:
   // up
   e.d--;
   if(a[(S.top->x - 1) * Edge + S.top->y] <= 0 && S.top->lsx != (e.x - 1) && S.array[(S.top->x - 1) * Edge + S.top->y] == false)
   {
    e.x--;
    S.array[(S.top->x - 1) * Edge + S.top->y] = true;
    return true;
   }
   break;
   /*
   //   4         ,           ,  nl   ,        
   else 
   {
    S.top->nl = true;
    // cout << "      ..." << endl;
    return false;
   }b
   /*/
   //*
  default:
   S.top->nl = true;
   return false;
   //*/
  }
 }
 return false;
}
void Patch (int a[], Datastore &d, SqStack &S) {
 // a[d.x*Edge + d.y];
 while(a[S.top->x*Edge + S.top->y] != -1)
 {
  if(NextPos(a, S, d))
  {
   Push(S, d);
   //        S.top   
   (S.top-1)->d = S.top->d;
   //   top         
   S.top->d = d.d = 4;
   //    top x y          
   d.lsx = S.top->x;
   d.lsy = S.top->y;
  }
  else
  {
   while(S.top->nl)
   {
    Datastore td;
    //          ,nl true,  
    Pop(S, td);
    d = *S.top;
    d.lsx = d.x;
    d.lsy = d.y;
    /*
    //    ,top     ,    top     d            d
    d.d = S.top->d;
    //    ,       d       top     
    //              d     
    d.lsx = d.x = S.top->x;
    d.lsy = d.y = S.top->y;
    //*/
   }
   if(S.top->x == Startx && S.top->y == Starty)
   {
    //               ,      
    cout << "error!     " << endl;
    return;
   }
  }
 }
 //a[d.x*Edge + d.y] = 1;
}
//       
//*
void Jugedir (Link top, char dir[])
{
 switch(top->d)
 {
 case 3:
  strcpy(dir,"Right<  >");
  break;
 case 2:
  strcpy(dir,"Down<  >");
  break;
 case 1:
  strcpy(dir,"Left<  >");
  break;
 case 0:
  strcpy(dir,"Up<  >");
 }
}
//*/
void PrintMaze (SqStack &S) {
 SqStack Sq;
 InitStack(Sq);
 //     
 for(;S.top != S.base;S.top--)
 {
  *(++Sq.top) = *S.top;
 }
 Sq.count = 1;//     
 //                 
 for(;Sq.top != Sq.base;Sq.top--,Sq.count++)
 {
  char dir[10];
  Jugedir(Sq.top, dir);
  cout << "(" << Sq.top->x << "," << Sq.top->y << "," << dir << ") " << "/t";
  if(Sq.count%2 == 0)
   cout << endl;
 }
 cout << endl;
 cout << "  " << S.count << " ..." << endl;
}
 
void main()
{
 int maze[Edge][Edge] = {
  //  1 2  3  4  5  6  7  8
  { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
  { 1, 0, 1, 0, 1, 0, 1, 1, 1, 1}, // 1
  { 1, 0, 0, 0, 0, 0, 0, 0, 0, 1}, // 2
  { 1, 1, 1, 1, 1, 1, 0, 1, 0, 1}, // 3
  { 1, 0, 0, 0, 0, 0, 0, 1, 0, 1}, // 4
  { 1, 0, 1, 0, 1, 1, 1, 1, 0, 1}, // 5
  { 1, 0, 0, 0, 0, 0, 0, 0, 0, 1}, // 6
  { 1, 0, 1, 1, 1, 1, 1, 1, 1, 1}, // 7
  { 1, 0, 0, 0, 0, 0, 0, 0,-1, 1}, // 8
  { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
 };
//*
 for(int i=0; i<Edge; i++)
  for(int j=0; j<Edge; j++)
  {
   if (j==0) cout << endl;
   cout << maze[i][j] << "  ";
  }
 cout << endl;
//*/
 Datastore d;
 InitDatastore(d);
 SqStack S;
 InitStack(S);
 Push(S, d);
 Patch(maze[0], d, S);
 PrintMaze(S);
 // DestroyStack(S);
}