求解答,迷宫求解
迷宫求解,运行后程序不输出修改后的地图,具体也不知道程序具体错在哪里#include "stdafx.h"#include "stdlib.h"
#define STACK_INIT_SIZE 100
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define STACKIN 10
typedef int Status;
typedef int MazeType;
typedef struct {
int x;
int y;
}PosType;
typedef struct {
int ord;
PosType seat;
int di;
}SElemType;
typedef struct {
SElemType * base;
SElemType * top;
int stacksize;
}SqStack;
SqStack S;
Status InitStack(SqStack &S) {
S.base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));
if (!S.base)exit(EOVERFLOW);
S.top = S.base;
S.stacksize = STACK_INIT_SIZE;
return OK;
};//构造空栈
Status DestroyStack(SqStack &S) {
free(S.base);
S.base = NULL;
S.top = NULL;
S.stacksize = 0;
return 0;
};//销毁栈
int StackLength(SqStack S) {
return S.top - S.base;
};//返回栈的长度
Status StackEmpty(SqStack S) {
if (S.base == S.top)
return TRUE;
else
return FALSE;
};//若栈S为空,返回TRUE,否则返回FALSE
Status StackFull(SqStack S) {
if (S.top - S.base >= S.stacksize)
return TRUE;
else
return FALSE;
};//若栈S为满,返回TRUE,否则返回FALSE
Status GetTop(SqStack S, SElemType &e) {
if (S.top == S.base) return ERROR;
e = *(S.top - 1);
return OK;
};//若栈不空,用e返回返回S的栈顶元素,并返回OK,否则返回ERROR
Status Pop(SqStack &S, SElemType &e) {
if (!StackEmpty(S))return FALSE; //判断栈是否为空
e = *--S.top;
S.top--;
return OK;
};//若栈不空,用e返回栈顶的值返回TRUE否则返回FALSE
Status Push(SqStack &S, SElemType e) {
if (StackFull(S))
{
S.base = (SElemType *)realloc(S.base, (S.stacksize + STACKIN) * sizeof(SElemType));
if (!S.base)exit(EOVERFLOW);
S.top = S.base + S.stacksize;
S.stacksize += STACKIN;
}
*S.top++ = e;
return OK;
};//插入e为栈顶元素
int Pass(PosType coordinate, MazeType passmaze[10][10]) {
if (passmaze[coordinate.x][coordinate.y] == 1)
return OK;
else
return FALSE;
};//判断当前位置是否可通过
void FootPrint(PosType coordinate, MazeType footmaze[10][10]) {
footmaze[coordinate.x][coordinate.y] = 2;
};//留下足迹
int comper(PosType a1, PosType a2) {
if (a1.x == a2.x && a1.y == a2.y)
{
return TRUE;
}
else
return FALSE;
};//PosType结构体之间的比较函数
PosType NextPos(PosType coordinate, Status x) {
switch (x)
{
case 1:
coordinate.y += 1;
break;
case 2:
coordinate.x += 1;
break;
case 3:
coordinate.x -= 1;
break;
case 4:
coordinate.y -= 1;
break;
}
return coordinate;
};
void MarkPrint(PosType coordinate, MazeType markmaze[10][10]) {
markmaze[coordinate.x][coordinate.y] = 3;
};
Status MaxePath(MazeType maze[10][10], PosType start, PosType end) {
PosType curpos;
InitStack(S);
int curstep = 1;
SElemType e;
curpos = start;
do
{
if (Pass(curpos, maze)) {
FootPrint(curpos, maze);
e.ord = curstep;
e.seat = curpos;
e.di = 1;
Push(S, e);
if (comper(curpos, end)) return TRUE;
curpos = NextPos(curpos, 1);
curstep++;
}
else {
if (!StackEmpty(S))
{
Pop(S, e);
while (e.di == 4 && !StackEmpty(S))
{
MarkPrint(curpos, maze);
Pop(S, e);
}
if (e.di < 4) {
e.di++;
Push(S, e);
curpos = NextPos(e.seat, e.di);
}
}
}
} while (!StackEmpty(S));
return FALSE;
};
void printfmaze(MazeType maze[10][10]) {
for (int i = 0; i < 10; i++) {
for (int j = 0; j < 10; j++)
{
printf("%d ", maze[i][j]);
}
printf("\r\n");
}
}//输出地图
int main()
{
PosType start, end;
MazeType maze[10][10] = {
{ 0,0,0,0,0,0,0,0,0,0 },
{ 0,1,0,0,0,1,1,0,0,0 },
{ 0,1,1,1,1,1,0,0,0,0 },
{ 0,0,0,1,0,0,0,0,0,0 },
{ 0,0,0,1,0,0,0,0,0,0 },
{ 0,0,1,1,0,0,0,0,0,0 },
{ 0,0,0,1,1,1,1,1,0,0 },
{ 0,0,0,0,0,0,0,1,0,0 },
{ 0,0,0,0,0,0,0,1,1,0 },
{ 0,0,0,0,0,0,0,0,0,0 },
};
start.x = 1; start.y = 1;
end.x = 8; end.y = 8;
printfmaze(maze);
if (MaxePath(maze, start, end) )
{
printfmaze(maze);
}
else
{
printf("迷宫不可解");
}
scanf_s("");
return 0;
}