数据结构C语言迷宫求解问题(有要求和源代码).doc

1、 迷宫求解
设计一个迷宫求解程序，要求如下：
ü 以M × N表示长方阵表示迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。
ü 能任意设定的迷宫
ü （选作）如果有通路，列出所有通路
提示：
ü 以一个二维数组来表示迷宫，0和1分别表示迷宫中的通路和障碍，如下图迷宫数据为：

1111111111
1001000101
1001000101
1000011001
1011100001
1000100001
1010001001
1011101101
1100000001
1111111111
入口位置：1 1
出口位置：8 8
ü 探索过程可采用如下算法，设定当前位置的初值为入口位置；
do {
若当前位置可通，
则｛
将当前位置插入栈顶；
　若该位置是出口位置，则结束；
　否则切换当前位置的东邻方块为新的当前位置；
　 ｝
否则，
｛
　　若栈不空且栈顶位置尚有其他方向未经探索，
　　则设定新的当前位置为沿顺时针方向旋转找到的栈顶位置的下一相邻块；
　　若栈不空但栈顶位置的四周均不可通，
　　则｛删去栈顶位置；　　//从路径中删去该通道块
　　　　　　　　若栈不空，则重新测试新的栈顶位置，
直至找到一个可通的相邻块出栈至栈空；
｝
｝
｝while (栈不空)；

#include<stdio.h>
#include<string.h>
#define MaxSize 32
int a[30][30];
int b[30][30];
int m,n;
typedef struct
{
int i;
int j;
int di;
}Box;
typedef struct
{
Box data[MaxSize];
int top;
}StackType;

bool sereach(int X,int Y,int X1,int Y1);

void main()
{
int X,Y,Y1,X1;
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
// for()
printf("请输入迷宫的长度和宽度\n");
while(~scanf("%d%d",&m,&n)){
printf("请输入迷宫（0表示空地，1表示围墙）\n");
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
scanf("%d",&a[i][j]);
if(a[i][j]==1)
b[i][j]=-1;
}
}
printf("请输入迷宫起点的行号和列号\n");
scanf("%d%d",&X,&Y);
printf("请输入迷宫终点的行号和列号\n");
scanf("%d%d",&X1,&Y1);
if(!sereach(X,Y,X1,Y1))
printf("该迷宫没有解!\n");
printf("请输入迷宫的长度和宽度\n");
}
// return 0;
}

bool sereach(int X,int Y,int X1,int Y1)
{
StackType st;
int i,j,di,find;
st.top=-1;
while(a[X][Y]!=0)
{
printf("迷宫起点的行号和列号有错，请重新输入\n");
scanf("%d%d",&X,&Y);
}
if(a[X][Y]==0)
b[X][Y]=-1;

while(a[X1][Y1]!=0)
{
printf("迷宫终点的行号和列号有错，请重新输入\n");
scanf("%d%d",&X1,&Y1);
}
st.top++;
st.data[st.top].i=X;
st.data[st.top].j=Y;
st.data[st.top].di=-1;
do{
find=0;
i=st.data[st.top].i;
j=st.data[st.top].j;
di=st.data[st.top].di;
while(di<4&&find==0)
{
di++;
switch(di)
{
case 0:i=st.data[st.top].i-1;j=st.data[st.top].j;break;
case 1:i=st.data[st.top].i;j=st.data[st.top].j+1;break;
case 2:i=st.data[st.top].i+1;j=st.data[st.top].j;break;
case 3:i=st.data[st.top].i;j=st.data[st.top].j-1;break;
}
if(b[i][j]==0&&i>=0&&i<n&&j>=0&&j<m)
find=1;
}
if(find == 1)
{
st.data[st.top].di=di;
st.top++;
st.data[st.top].i=i;
st.data[st.top].j=j;
st.data[st.top].di=-1;
b[i][j]=-1;
find=0;
}
else
{
b[st.data[st.top].i][st.data[st.top].j]=0;
st.top--;
}
if(i==X1&&j==Y1)
{printf("迷宫路径如下:\n");
for(int k=0;k<=st.top;k++)
{printf("%d,%d\t",st.data[k].i,st.data[k].j);
if((k+1)%6==0)
printf("\n");
}
printf("\n");
return true;
}
}
while(st.top>-1);
return false;
}

宁波工程学院 计科12-1班