Question

关于数据结构的题目，如能回答，在下感激不尽

标题： 迷宫问题
时 限： 100000 ms
内存限制： 100000 K
总时限： 300000 ms
描述： 迷宫问题

迷宫是一个二维矩阵,其中1为墙,0为路,3为入口,4为出口.要求从入口开始,从出口结束,按照 下,左,上,右 的顺序来搜索路径.
输入： 迷宫宽度w 迷宫高度h
迷宫第一行
迷宫第二行
...
迷宫第h 行
输出： 入口横坐标1 入口纵坐标1
横坐标2 纵坐标2
横坐标3 纵坐标3
横坐标4 纵坐标4
...
横坐标n-1 纵坐标n-1
出口横坐标n 出口纵坐标n
输入样例： 8 10
1 1 1 1 1 1 1 1
1 0 1 1 0 1 0 1
1 0 1 0 0 1 0 1
1 1 0 3 1 0 1 1
1 0 0 1 0 0 4 1
1 0 0 0 0 1 1 1
1 0 1 0 0 1 0 1
1 0 1 0 0 0 1 1
1 1 1 1 0 0 0 1
1 1 1 1 1 1 1 1
输出样例： 3 3
2 3
2 4
2 5
3 5
3 6
3 7
4 7
4 6
4 5
4 4
5 4
6 4

提示： 使用栈

参见教材 50 页

Answer 1

#include <stdio.h>
#include <stdlib.h>
#define InitStackSize 1000
#define SizeIncrease 100

typedef struct
{
int x;
int y;

}PosType;

typedef struct
{
int ord;
PosType seat;
int di;
}SElemType;

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

//initial stack
int InitStack(sqStack *s)
{
s->base=(SElemType*)malloc(InitStackSize*sizeof(SElemType));
s->top=s->base;
s->stacksize=InitStackSize;
return 0;
}

//push
int Push(sqStack *s,SElemType e)
{
if(s->top-s->base>=s->stacksize)//stack is full,realloc
{
//printf("realloc\n");
s->base=(SElemType*)realloc(s->base,(s->stacksize+SizeIncrease)*sizeof(SElemType));
s->top=s->base+s->stacksize;
s->stacksize=s->stacksize+SizeIncrease;
}
*(s->top)=e;
s->top++;
return 0;
}

//pop
SElemType pop(sqStack *s)
{
SElemType temp;
s->top--;
temp=*(s->top);
return temp;
}

//gettop
SElemType gettop(sqStack *s)
{
return *(s->top-1);
}

//isempty
int isempty(sqStack *s)
{
if(s->top==s->base)
return 1;
else
return 0;
}

//Traverse
//int StackTraverse(sqStack *s)
//{
//SElemType *p=s->top;
////printf("该栈自顶向下的元素为:\n");
//while(p!=s->base)
//{
//p--;
////cout<<*p<<endl;
//printf("(%d %d)",p->seat.y,p->seat.x);
//}
//printf("\n");
//return 0;
//}

void printffrombase(sqStack *s)
{
SElemType *p=s->base;
while(p!=s->top)
{
printf("%d %d\n",p->seat.x,p->seat.y);
p++;
}
}

int Pass(int **Maze,PosType pos)
{
if(Maze[pos.y][pos.x]!=1)
return 1;
return 0;
}

void Footprint(int **Maze,PosType pos)
{
//pos->walked=1;
Maze[pos.y][pos.x]=1;
}

void Markprint(int **Maze,PosType pos)
{
Maze[pos.y][pos.x]=1;
}

PosType NextPos(PosType curpos,int di)
{
if(di==1)
{
curpos.y=curpos.y+1;
}
if(di==2)
{
curpos.x=curpos.x-1;
}
if(di==3)
{
curpos.y=curpos.y-1;
}
if(di==4)
{
curpos.x=curpos.x+1;
}
return curpos;

}

int main()
{
int width,height;
scanf("%d%d",&width,&height);

//动态分配迷宫的宽和高
int **Maze;
Maze=(int **)malloc(sizeof(int*)*height);
Maze[0]=(int *)malloc(sizeof(int)*height*width);
int i;
for(i=1;i<height;i++)
{
Maze[i]=Maze[i-1]+width;
}
//获取迷宫各位置的值
int temp;
for (i=0;i<height;i++)
{
int j;
for(j=0;j<width;j++)
{
scanf("%d",&temp);
//setPos(&pos[i][j],j,i,temp);
Maze[i][j]=temp;
}
}

sqStack *stack=(sqStack*)malloc(sizeof(sqStack));
InitStack(stack);
PosType curpos,start,end;

int j;
for(i=0;i<height;i++)
{
for(j=0;j<width;j++)
{
if(Maze[i][j]==3)
{
start.x=j;
start.y=i;
}
}
}
for(i=0;i<height;i++)
{
for(j=0;j<width;j++)
{
if(Maze[i][j]==4)
{
end.x=j;
end.y=i;
}
}
}

int curstep=1;
curpos=start;
do
{
if(Pass(Maze,curpos))
{
Footprint(Maze,curpos);
SElemType e;
e.ord=curstep;
e.seat=curpos;
e.di=1;
Push(stack,e);

if(curpos.x==end.x&&curpos.y==end.y)
{
//printf("12\n");
printffrombase(stack);
return 0;
}
curpos=NextPos(curpos,1);
curstep++;
}//if pass
else
{
//printf("nopass\n");
if(!isempty(stack))
{
SElemType e=pop(stack);
while(e.di==4 && !isempty(stack))
{
Markprint(Maze,e.seat);
e=pop(stack);
}//while
if(e.di<4)
{
e.di++;
Push(stack,e);
curpos=NextPos(e.seat,e.di);
}//if
}//if
}//else
}while(!isempty(stack));
return 1;
}