# 迷宫问题（一）-利用栈回溯

```#include<stdio.h>
#include <stdlib.h>
#define OK      1
#define ERROR   0
#define TRUE    1
#define FALSE   0
#define OVERFLOW -1
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 20
#define N 10

typedef int Status;
typedef char MazeType[N][N + 1];

int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};

typedef struct {
int x; //迷宫中的行
int y; //迷宫中的列
} PosType; //坐标

typedef struct {
PosType      seat;    //当前的坐标位置
int   di;        //往下一个坐标位置的方向
} SElemType; //栈的元素类型

typedef struct {
SElemType *base;
SElemType *top;
int stacksize;
} SqStack;

Status 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;
}

Status 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;
return OK;
}

Status Pop(SqStack &s, SElemType &e)
{
if(s.top == s.base)return ERROR;
e = * --s.top;
return OK;
}

int StackEmpty(SqStack s)
{
return s.base == s.top;
}

Status Pass(MazeType maze, PosType curpos) //判断当前节点是否通过
{
return maze[curpos.x][curpos.y] == ‘ ‘ || maze[curpos.x][curpos.y] == ‘S‘
|| maze[curpos.x][curpos.y] == ‘E‘;
}

void FootPrint(MazeType &maze, PosType curpos) //留下足迹
{
maze[curpos.x][curpos.y] = ‘*‘; //走过且走得通
}

PosType NextPos(PosType pos,int d){
pos.x += dx[d];
pos.y += dy[d];
return pos;
}

void MarkPrint(MazeType &maze, PosType curpos) //留下不能通过的标记
{
maze[curpos.x][curpos.y] = ‘!‘; //走过但走不通
}

//求解迷宫maze中,从入口start到出口end的一条路径
Status MazePath(MazeType &maze, PosType start, PosType end)
{
SqStack s;
SElemType e;
InitStack(s);
PosType curpos = start;
do {
if(Pass(maze, curpos)) { //如果当前位置可以通过,即是未曾走到的通道块
FootPrint(maze, curpos);     //留下足迹
if(curpos.x==end.x && curpos.y==end.y)
return TRUE;
e.seat = curpos;
e.di = 0;
Push(s, e);
curpos = NextPos(curpos, 0);  //获得下一节点:当前位置的东邻
}
else { //当前位置不能通过
if(!StackEmpty(s)) {
Pop(s, e);
while(e.di == 3 && !StackEmpty(s)) {
MarkPrint(maze, e.seat);
Pop(s, e);  //留下不能通过的标记,并退回一步
}
if(e.di < 3) {
e.di++;
Push(s, e);           //换一个方向探索
curpos = NextPos(e.seat, e.di);   //设定当前位置是该方向上的相邻块
}//if
}//if
}//else
} while(!StackEmpty(s));
return FALSE;
}
int main()
{
int i;
PosType start={1, 1}, end={8,8};
MazeType maze;
for(i = 0; i < 10; i++)
gets(maze[i]);
MazePath(maze, start, end);
for(i = 0; i < 10; i++)
puts(maze[i]);
return 0;
}```

## zoj1004-Anagrams by Stack 【栈 回溯】

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4 Anagrams by Stack Time Limit: 2 Seconds      Memory Limit: 65536 KB How can anagrams result from sequences of stack operations? There are two sequences of stack operators which can convert

## 将中缀表达式转换为后缀表达式，然后利用栈对表达式求值。

<!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8"> <title>Title</title> <script src="js.js"></script> </head> <body> 输入中缀表达式空格分隔 例如 2 + 3 <input type=