#include<stdio.h>
#include<stdlib.h>
#define m 10
#define n 10
#define STACK_INIT_SIZE 100
typedef struct
{
int x,y;
}SElemType;
typedef struct
{
SElemType stack[STACK_INIT_SIZE];
int top;
}SqStack;
typedef struct
{
int x,y;
}Item;
int maze[m][n]=
{
/0,1,2,3,4,5,6,7,8,9/
/0/ {1,1,1,1,1,1,1,1,1,1},
/1/ {1,0,1,0,0,0,0,0,0,1},
/2/ {1,0,0,0,1,1,1,1,0,1},
/3/ {1,0,1,0,0,0,1,0,0,1},
/4/ {1,0,0,1,1,0,1,1,0,1},
/5/ {1,0,1,0,1,0,0,0,0,1},
/6/ {1,0,0,0,0,0,1,1,0,1},
/7/ {1,1,1,0,1,1,1,1,0,1},
/8/ {1,1,0,0,0,0,0,0,0,1},
/9/ {1,1,1,1,1,1,1,1,1,1},
};
int t[m][n]={0}; //与迷宫相同的二维数组,用来表示该条路有没有走;
Item Move[4]= //记录走的方向;
{
{0,1},{1,0},
{0,-1},{-1,0}
};
int sum=0; //记录有几条路径
//打印路径
void Print(int sum,SqStack a)
{
int i,p,k;
printf("迷宫的第%d条路径如下:\n",sum);
for(i=0;i<=a.top;i++)
printf("(%d,%d)->",a.stack[i].x,a.stack[i].y);
printf("出口\n\n");
for(p=0;p<10;p++){
printf("\t\t");
for(k=0;k<10;k++){
if(maze[p][k]==1){
printf("#");
}else if(maze[p][k]==0){
printf(" ");
}else{
printf("o");
}
}
if(k==10){
printf("\n");
}
}
printf("\n");
}
//符合规则的压入栈
void Push_SqStack(SqStack *s,SElemType x)
{
if(s->top==STACK_INIT_SIZE-1)
printf("\n栈满!");
else
{
s->top++;
s->stack[s->top]=x;
}
}
//检查栈是否为空
int Empty_SqStack(SqStack *s)
{
if(s->top==-1)
return 1;
else
return 0;
}
//删除栈顶的元素,退后操作
void Pop_SqStack(SqStack *s)
{
if(Empty_SqStack(s))
{
printf("\n栈空!");
exit(0);
}
else
{
s->top--;
}
}
void path(int x,int y,SqStack elem)
{
int i,a,b;
SElemType temp;
if(x==8&&y==8)
{
sum++;
Print(sum,elem);
}
else
{
for(i=0;i<4;i++) //遍历四个方向
{
a=x+Move[i].x;
b=y+Move[i].y;
if(maze[a][b]==0&&t[a][b]==0)
{
temp.x=a;temp.y=b;
t[a][b]=maze[a][b]=-1; //用数组t,M记录这个位置已经走过了
Push_SqStack(&elem,temp);
path(a,b,elem);
t[a][b]=maze[a][b]=0; //回溯之后需要将这个位置清空,表示这条路没有走过
Pop_SqStack(&elem);
}
}
}
}
int main()
{
SqStack *s;
s=(SqStack *)malloc(sizeof(SqStack));
s->stack[0].x=1;
s->stack[0].y=1;
s->top=0;
t[1][1]=maze[1][1]=-1;
path(1,1,*s);
return 0;
}
这段代码实现了一个求解迷宫问题的算法。算法的思想是使用一个栈来存储路径上的位置,从起点开始依次向四个方向搜索,如果遇到障碍或者已经搜索过的位置就退回到上一个位置继续搜索,直到找到出口为止。
主函数的作用是初始化栈,设定起点和出口的位置,然后调用搜索函数求解迷宫问题。