迷宫MAZE数据结构介绍

迷宫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);
}