#include
#include
#include
int maze[100][100];//定义最大迷宫数组
int m,n;//定义行列
typedef struct pos//定义位置的结构体
{
int x;//定义行
int y;//定义列
}pos;
typedef struct//定义顺序栈
{
pos base[100];//定义顺序栈存储结构
int top;//头指针
}stack;
int isEmpty(stack);//定义判断栈是否为空的函数
void push(stack *,int,int);//入栈
void pop(stack *,int *,int *);//出栈
int isEmpty(stack s1)//判断栈是否为空的函数
{
if(s1.top==0)//当头指针指向首地址时栈为空并返回1
return 1;//返回1
return 0;//否则返回0
}
void push(stack *s1,int x,int y)//入栈
{
(s1->base[s1->top]).x=x;//将当前行坐标存入栈
(s1->base[s1->top]).y=y;//y同上
s1->top++;//指针指向下一个位置
}
void pop(stack *s1,int *x,int *y)//出栈
{
s1->top--;//指针指向前一个位置
*x=(s1->base[s1->top]).x;//将当前行坐标赋给x所指向的元素
*y=(s1->base[s1->top]).y;//y同上
}
void main()//主函数
{
void InitMaze();//初始化迷宫
void printMaze();//打印迷宫
void FindPath();//找路径
while(1)
{
printf("请输入迷宫的行数m(大于0，小于100):");
scanf("%d",&m);
printf("请输入迷宫的列数n(大于0，小于100):");
scanf("%d",&n);
if(m<0||m>100||n<0||n>100)
{
printf("输入数据错误,重新输入\n");
continue;//输错时重新执行while语句
}
InitMaze();//初始化迷宫
printf("原迷宫为:\n");
printMaze();//打印迷宫
FindPath();//找路径
}
}
void InitMaze()//初始化迷宫函数
{
int i,j,temp;//定义
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
{
temp=rand()%100+1;//随机产生1——100的随机数
if(temp>30)//如果随机数大于30
{
maze[i-1][j-1]=0;//当前数组值为0
}else
{
maze[i-1][j-1]=1;//否则1
}
}
maze[0][0]=0;//入口为0
maze[m-1][n-1]=7; //特殊的通路
}
void printMaze()//打印函数
{
int i=0,j=0;//定义
for(i=0;i
printf(" %d",i+1);
}
printf("\n");
for(i=0;i
printf(" %d",i+1);
for(j=0;j
if(maze[i][j]==0||maze[i][j]==7||maze[i][j]==-1)//如果等于上述值
{
printf("□");//通路
}
else if(maze[i][j]==1)
{
printf("■");//墙
}
else if(maze[i][j]==2) //2是→
{
printf("→");
}
else if(maze[i][j]==3) //3是↓
{
printf("↓");
}
else if(maze[i][j]==4) //4是←
{
printf("←");
}
els
e if(maze[i][j]==5) //5是↑
{
printf("↑");
}
}
printf("\n");
}
}
void FindPath()//找路函数
{
int posx=0,posy=0;//定义当前位置行列坐标
int flag=0; //是否到达出口
stack s;//定义栈
int pass(int,int);//定义方向函数
s.top=0; //栈的头指针为0
do
{
if(maze[posx][posy]==7)//判断该位置是否为出口位置
{
maze[posx][posy]=2;//？？？？？？？？？？？？向右指？？？？？？？？？？？//
flag=1;//路找完了
}
switch(pass(posx,posy))//判断可行方向
{
case 2:
maze[posx][posy]=2;
push(&s,posx,posy);
posy++;
break; //向右可行,将可行的位置压入栈,改其右边的位置为当前要判断的位置
case 3:
maze[posx][posy]=3;
push(&s,posx,posy);
posx++;
break;//同上
case 4:
maze[posx][posy]=4;
push(&s,posx,posy);
posy--;
break;//同上
case 5:
maze[posx][posy]=5;
push(&s,posx,posy);
posx--;
break;//同上
case -1:
maze[posx][posy]=-1;
if(!isEmpty(s))
pop(&s,&posx,&posy);
break;//没路，出栈
}
}
while(!isEmpty(s)&&flag==0);//栈空跳出循环，打印无解
if(flag==1)//有路，输出路径
{
printf("该迷宫的行走路径如下:\n");
printMaze();
printf("\n程序结束");
exit(1);//跳出所有程序
}
else
{
printf("\n该迷宫无解\n");
}
}
int pass(int i,int j) //坐标(i.j),返回可行的方向
{
if(j
return 2;
}
if(i
return 3;
}
if(j>0&&(maze[i][j-1]==0||maze[i][j-1]==7)) //不是最左边的位置,左为0可通行
{
return 4;
}
if(i>0&&(maze[i-1][j]==0||maze[i-1][j]==7)) //不是最上边的位置,上为0可通行
{
return 5;
}
return -1; //上下左右都不能通行
}