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

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