数据结构 迷宫 代码

#include<stdio.h>

#include<iostream>

#include<stdlib.h>

#include<time.h>

#define STACK_INIT_SIZE 1000

#define STACKINCREMENT 10

#define OK 1

#define OVERFLOW 0

#define ERROR 0

//typedef int SElemType;

typedef struct SElemType{

int x;int y;

};

typedef struct{

SElemType *base;

SElemType *top;

int stacksize;

}SqStack;

int InitStack(SqStack &S){

S.base=(SElemType *)malloc(STACK_INIT_SIZE *sizeof(SElemType));

if(!S.base) exit(OVERFLOW);

S.top=S.base;

S.stacksize=STACK_INIT_SIZE;

return OK;

}

void Push(SqStack &S,SElemType &e){

if(S.top-S.base>=S.stacksize){

S.base=(SElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));

if(!S.base) exit (OVERFLOW);

S.top=S.base+S.stacksize;

S.stacksize+=STACKINCREMENT;

}

*S.top++=e;

}

SElemType Pop(SqStack &S,SElemType &e){

//if(S.top==S.base) return ERROR;

e=*--S.top;

return e;

}

SElemType GetTop(SqStack S,SElemType &e){

e=*(S.top-1);

return e;

}

int StackEmpty(SqStack &S)

{//若栈S为空栈，则返回OK，否则返回ERROR

if(S.base==S.top)

return OK;

else

return ERROR;

}

int main()

{

int m;

SqStack S;

InitStack(S);

printf("请输入迷宫的大小(m*m)");

scanf("%d",&m);

//数组的形式表示八个方向

int move[8][2]={{0,1},{1,1},{1,0},

{1,-1},{0,-1},{-1,-1},{-1, 0},{-1, 1}};

//用结构体表示位置

struct position

{

int x,y;

};

//用于记录和输出迷宫探路中相关符号，包括1 .

char maze[20][20];

//用栈来存储探路过程中的数据

int i,x,y,ok;

SElemType p;

//二维数组的第0行、第m+1行、第0列、第m+1列元素全

//置成“1”，表示迷宫的边界；第1行第1列元素和第m行第m列

//元素置成“0”，表示迷宫的入口和出口；其余元素值用随机

//函数产生。

srand(time(0));

for(x=1;x<=m;x++)

for(y=1;y<=m;y++)

maze[x][y]=48+rand()%2;

maze[1][1]='0';maze[m][m]='0';

for(x=0;x<=m+1;x++)

{

maze[x][0]='1';maze[x][m+1]='1';

}

for(y=0;y<=m+1;y++)

{

maze[0][y]='1';maze[m+1][y]='1';

}

p.x=1;p.y=1;

Push(S,p);

maze[1][1]='.';

printf("迷宫初始为（m*m）/n");

for(x=1;x<=m;x++)

{

printf("/n");

for(y=1;y<=m;y++)

printf("%c ",maze[x][y]);

}

printf("/n");

//开始探路

do{

GetTop(S,p);

ok=0;i=0;

while((ok==0)&&(i<8))

{

x=p.x+move[i][0];

y=p.y+move[i][1];

if(maze[x][y]=='0')

{

p.x=x;p.y=y;

Push(S,p);

maze[x][y]='.';

ok=1;

}

i++;

}

if(i==8)

{

maze[p.x][p.y]='*';

Pop(S,p);

}

}while((!StackEmpty(S))&&((p.x!=m)||(p.y!=m)));

//输出探路结果

if(StackEmpty(S)) printf("没有路径/n");

else printf("有路径/n");

//输出探路迷宫留下的踪迹

for(x=1;x<=m;x++)

{

printf("/n");

for(y=1;y<=m;y++)

printf("%c ",maze[x][y]);

}

printf("/n");

system("pause");

}