#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);
}
