# 数据结构-栈的应用-迷宫问题

## Maze Problem

Posted by xuepro on November 10, 2017

## —基于堆栈的迷宫问题代码—

#define OK 0
#define ERROR -1
#include <stdio.h>

/*
int maze[7][7] = {
1, 1, 1, 1, 1, 1, 1,
1, 0, 1, 0, 0, 0, 1,
1, 0, 1, 0, 1, 0, 1,
1, 0, 0, 0, 0, 0, 1,
1, 0, 1, 1, 1, 0, 1,
1, 0, 0, 0, 1, 0, 1,
1, 1, 1, 1, 1, 1, 1
};
*/

int maze[7][7] = {
1, 1, 1, 1, 1, 1, 1,
1, 0, 0, 0, 1, 0, 1,
1, 0, 0, 1, 0, 1, 1,
1, 0, 1, 0, 0, 0, 1,
1, 0, 0, 0, 1, 0, 1,
1, 0, 0, 1, 1, 0, 1,
1, 1, 1, 1, 1, 1, 1
};
typedef struct
{
int i;
int j;
int direction; //0表示其四周为探索过，1,2,3,4分别表示其东南西北已经探索过。
} Position;

Position *end = 0;

int canGo(Position pos) {
if(maze[pos.i][pos.j] == 0) return OK;
return ERROR;
}

int isExitPos(Position pos) {
if (pos.i == end->i &&pos.j == end->j) return OK;
return ERROR;
}

//--------------Stack start---------------
#include <malloc.h>

typedef Position  ElemType;
typedef struct {
ElemType *base;
ElemType *top;
int       capacity;
} SqStack;

int InitStack(SqStack *S,int cap) {
S->base = (ElemType*)malloc(cap * sizeof(ElemType)); //分配空间
if (!S->base)	return ERROR;
S->top = S->base;           //设置指针
S->capacity = cap;  //设置大小
return OK;
}

int Push(SqStack *S, ElemType e) {
if (S->top - S->base >= S->capacity) {//若空间不够，重新分配
S->base = (ElemType *)realloc
(S->base, 2*S->capacity*sizeof(ElemType));
if (!S->base) return ERROR;
S->top = S->base + S->capacity;
S->capacity *=2;
}
*S->top++ = e; //插入数据
return OK;
}

int Pop(SqStack *S, ElemType *e)
{
if (S->top == S->base)  //空栈
return ERROR;
*e = *--S->top;       //出栈
return OK;
}

int Top(SqStack S, ElemType *e)
{
if (S.top == S.base)  //空栈
return ERROR;
*e = *(S.top - 1);       //出栈
return OK;
}

int IsEmpty(SqStack S) {
if(S.top == S.base) return 1;
return 0;
}
//---------------Stack end----------------------

/*从cur_pos的四周找一个可前进的方向next_pos*/
int gotoNextPos(Position *cur_pos, Position *next_pos) {
if ( isExitPos(*cur_pos)==OK) return ERROR;

next_pos->i = cur_pos->i;
next_pos->j = cur_pos->j;
next_pos->direction = 0;
while (cur_pos->direction < 4) {
switch (cur_pos->direction) {
case 0:  next_pos->i = cur_pos->i + 1;         break;
case 1:  next_pos->j = cur_pos->j + 1;         break;
case 2:  next_pos->i = cur_pos->i - 1;         break;
case 3:  next_pos->j = cur_pos->j - 1;         break;
}
cur_pos->direction++;
if (canGo(*next_pos)==OK) return OK;
}
return ERROR;
}

void makeFoot(Position pos) {
maze[pos.i][pos.j] = 2;
}

//输出逆向的路径
void printPath(SqStack *S) {
Position pos;
while (!IsEmpty(*S)) {
Pop(S, &pos);
printf("%d, %d\n",pos.i,pos.j);
}
}

void goMaze(Position start_pos) {
Position cur_pos, next_pos,temp_pos;
SqStack S;
InitStack(&S,20);
Push(&S, start_pos);
makeFoot(start_pos);

while (!IsEmpty(S)) {
Top(S, &cur_pos);
if (isExitPos(cur_pos)==OK) break; //出口
else if(gotoNextPos(&cur_pos, &next_pos)!=OK){ //栈顶位置不可通
Pop(&S, &cur_pos);
}
else{
//修改cur_pos表示已走到next_pos，并放回堆栈
Pop(&S, &temp_pos);
Push(&S, cur_pos);

Push(&S, next_pos);
makeFoot(next_pos); //留下足迹
}
}
printPath(&S);
}

int main() {
Position start_pos, end_pos;
start_pos.i = 1, start_pos.j = 1;
end_pos.i = 5, end_pos.j = 5;
end = &end_pos;
start_pos.direction = 0;
goMaze(start_pos);

return 0;
}


## —基于递归的迷宫问题代码—

#include <stdio.h>
#define OK 1
#define ERROR 0

int maze[7][7] = {
1, 1, 1, 1, 1, 1, 1,
1, 0, 1, 0, 0, 0, 1,
1, 0, 1, 0, 1, 0, 1,
1, 0, 0, 0, 0, 0, 1,
1, 0, 1, 1, 1, 0, 1,
1, 0, 0, 0, 1, 0, 1,
1, 1, 1, 1, 1, 1, 1
};

typedef struct Position_
{
int i;
int j;
} Position;

Position *end = 0;

int canGo(Position pos) {
return maze[pos.i][pos.j] == 0;
}

int isExitPos(Position pos) {
if (pos.i == end->i &&pos.j == end->j) return OK;
return ERROR;
}

Position pre_position[7][7] =
{
{ { -1,-1 },{ -1,-1 },{ -1,-1 },{ -1,-1 },{ -1,-1 },{ -1,-1 },{ -1,-1 } },
{ { -1,-1 },{ -1,-1 },{ -1,-1 },{ -1,-1 },{ -1,-1 },{ -1,-1 },{ -1,-1 } },
{ { -1,-1 },{ -1,-1 },{ -1,-1 },{ -1,-1 },{ -1,-1 },{ -1,-1 },{ -1,-1 } },
{ { -1,-1 },{ -1,-1 },{ -1,-1 },{ -1,-1 },{ -1,-1 },{ -1,-1 },{ -1,-1 } },
{ { -1,-1 },{ -1,-1 },{ -1,-1 },{ -1,-1 },{ -1,-1 },{ -1,-1 },{ -1,-1 } },
{ { -1,-1 },{ -1,-1 },{ -1,-1 },{ -1,-1 },{ -1,-1 },{ -1,-1 },{ -1,-1 } },
{ { -1,-1 },{ -1,-1 },{ -1,-1 },{ -1,-1 },{ -1,-1 },{ -1,-1 },{ -1,-1 } },
};

void makeFoot(Position pre_pos, Position pos) {
pre_position[pos.i][pos.j] = pre_pos; //记录路径
maze[pos.i][pos.j] = 2;
}

int goMaze(Position pre_pos,Position pos) {
if (canGo(pos)!=OK) return ERROR; //该位置是墙或已经探索过
makeFoot(pre_pos, pos);
if(isExitPos(pos)==OK) return OK; //已经走到出口，不再探索

Position next_pos;
next_pos.i = pos.i + 1; next_pos.j = pos.j;
if (goMaze(pos,next_pos)==OK) return OK;

next_pos.i = pos.i; next_pos.j = pos.j + 1;
if (goMaze(pos, next_pos)==OK) return OK;

next_pos.i = pos.i - 1; next_pos.j = pos.j;
if (goMaze(pos, next_pos)==OK) return OK;

next_pos.i = pos.i; next_pos.j = pos.j - 1;
if (goMaze(pos, next_pos)==OK) return OK;
return ERROR;
}

//输出逆向的路径

void printPath(Position start_pos, Position end_pos) {
for (Position pos = end_pos; pos.i != -1&&pos.j != -1;
pos = pre_position[pos.i][pos.j]) {
printf("%d, %d\n",pos.i,pos.j);
}
}
int main() {
Position start_pos, end_pos;
start_pos.i = 1, start_pos.j = 1;
end_pos.i = 5, end_pos.j = 5;
end = &end_pos;

Position pre_pos; pre_pos.i = -1; pre_pos.j = -1;
goMaze(pre_pos,start_pos);

printPath(start_pos, end_pos);

return 0;
}