展开全部#include
include
include
typedef struct pos/*描述迷宫当前位置和方向*/
{
int x;int y;int way;0:无效,1:左,2:下,3:右,4:上*/
}p;typedef struct linknode/*链表结构,用于栈的元素类型*/
{
p pos;struct linknode*next;}linknode;typedef struct stack/*链式栈,用于存储迷宫路径信息*/
{
linknode*head;头指针*/
}stack;int row=0;迷宫的行数*/
int line=0;迷宫的列数*/
void initstack(stack*s)/*栈置空*/
{
s->head=**;}
void push(stack*s,p p)/*数据入栈*/
{
linknode*ln=(linknode*)malloc(sizeof(linknode));ln->pos=p;ln->next=s->head;s->head=ln;}
p pop(stack*s)/*栈顶元素出栈*/
{
p pos;linknode*ln;ln=s->head;s->head=s->head->next;pos=ln->pos;delete ln;return pos;}
p getpop(stack s)/*读取栈顶元素*/
{
return s.head->pos;}
int empty(stack s)/*判空*/
{
if(s.head=**)
return 1;else
return 0;}
int*initmaze()/*返回迷宫的二维指针*/
{
int*maze=**;int i;int j;printf("请输入迷宫的行跟列(x,y):");scanf("%d,%d",&row,&line);输入迷宫的行和列*/
maze=(int*)malloc((row+2)*sizeof(int*));for(i=0;i;i+)
{
maze[i]=(int*)malloc(sizeof(int)*(line+2));}
printf("请输入迷宫\n");输入迷宫,1代表路障,0代表通行*/
for(i=1;i;i+)
for(j=1;j;j+)
scanf("%d",&maze[i][j]);for(i=0;i;i+)/*将迷宫的四周都变为1*/
maze[0][i]=1;for(i=0;i;i+)
maze[row+1][i]=1;for(i=0;i;i+)
maze[i][0]=1;for(i=0;i;i+)
maze[i][line+1]=1;for(i=0;i;i+)/*输出迷宫*/
{
for(j=0;j;j+)
printf("%3d",maze[i][j]);printf("\n");}
return maze;}
void printway(stack p)/*输出路径*/
{
p pos;stack t;临时栈,用于存储从入口到出口的路径*/
linknode*temp;int a,b;initstack(&t);temp=(linknode*)malloc(sizeof(linknode));temp->pos=pop(&p);取栈顶元素,即出口*/
push(&t,temp->pos);入栈*/
free(temp);while!empty(p))
{
temp=(linknode*)malloc(sizeof(linknode));temp->pos=pop(&p);获取下一个元素*/
a=getpop(t).x-temp->pos.x;左:a=0,b=1;下:a=1,b=0*/
b=getpop(t).y-temp->pos.y;右:a=0,b=-1 上:a=-1,b=0;if(b=1)
temp->pos.way=1;else if(a=1)
temp->pos.way=2;else if(b=-1)
temp->pos.way=3;else if(a=-1)
temp->pos.way=4;push(&t,temp->pos);新位置入栈*/
free(temp);}
printf("迷宫的路径为:\n");printf("前两个数字表示位置,最后一个数字表示方向\n");printf("1表示向左,2表示向下,3表示向右,4表示向上,0表示无方向\n");while!empty(t))/*输出路径*/
{
pos=pop(&t);printf("%3d,%3d,%3d\n",pos.x,pos.y,pos.way);}
}
int findmaze(int*maze,int r,int l)/*寻找路径,找到返回1,没找到返回0*/
{
stack p,q;栈p,q分别表示探索迷宫的路径和过程*/
p temp1,temp2;int a,b;initstack(&p);initstack(&q);temp1.x=1;temp1.y=1;maze[1][1]=-1;标记已经走过*/
push(&p,temp1);push(&q,temp1);while!empty(q))
{
temp2=getpop(q);if!(getpop(p).x=getpop(q).x
getpop(p).y=getpop(q).y))
push(&p,temp2);若有新元素入栈,就把q的栈顶元素存入p中*/
a=temp2.x;b=temp2.y+1;当前位置左方向相邻的方块*/
if(maze[a][b]=0)
{
temp1.x=a;temp1.y=b;maze[a][b]=-1;标记已走过*/
push(&q,temp1);}
if(a=r&b=l)/*到达出口*/
{
temp1.way=0;push(&p,temp1);printway(p);return 1;}
a=temp2.x+1;b=temp2.y;当前位置下方向相邻的方块*/
if(maze[a][b]=0)
{
temp1.x=a;temp1.y=b;maze[a][b]=-1;标记已走过*/
push(&q,temp1);}
if(a=r&b=l)/*到达出口*/
{
temp1.way=0;push(&p,temp1);printway(p);return 1;}
a=temp2.x;b=temp2.y-1;当前位置右方向相邻的方块*/
if(maze[a][b]=0)
{
temp1.x=a;temp1.y=b;maze[a][b]=-1;标记已走过*/
push(&q,temp1);}
if(a=r&b=l)/*到达出口*/
{
temp1.way=0;push(&p,temp1);printway(p);return 1;}
a=temp2.x-1;b=temp2.y;当前位置上方向相邻的方块*/
if(maze[a][b]=0)
{
temp1.x=a;temp1.y=b;maze[a][b]=-1;标记已走过*/
push(&q,temp1);}
if(a=r&b=l)/*到达出口*/
{
temp1.way=0;push(&p,temp1);printway(p);return 1;}
if(getpop(p).x=getpop(q).x
getpop(p).y=getpop(q).y)/*若四个方向都走不通,则数据出栈,退回一格*/
{
pop(&p);pop(&q);}
}
return 0;探索迷宫失败*/
}
void main()
{
int*maze=initmaze();初始化迷宫*/
if(findmaze(maze,row,line))/*探索路径*/
printf("路径探索成功!\n");else
printf("路径探索失败!\n");getch();}