离散数学 实验报告 迷宫最短路径问题求解
离散数学迷宫问题
问题描述：
一只老鼠走进了一个迷宫，这个迷宫是由M 行N 列（如:10行8列）的方格构成的，相邻方格之间可能是相通的，也可能有墙相隔，各方格位置由其对应坐标确定，如图所示。迷宫在（1，1）处有一个入口，在（M,N ）处有一个出口，在入口和出口之间有通路相通。问题是让你帮助老鼠找出从入口到出口的一条最短路径。
00001000
11001010
00010000
00001010
10100000
00111011
10001000
基本要求：
为老鼠找出一条从入口到出口的最短路径。
实现提示：
1、 迷宫用数组表示，1代表是墙走不通，0表示可以通行。边界可以扩充为墙，即M ×N 迷宫用(M+2)×(N+2)数组表示。
2、 向4个方向前进时的位移量可以用以下数组表示，处理是方便。
int move[4][2]={ {0,1},{1,0},{0,-1},{-1,0} };
3、 采用图的广度优先搜索算法。
#include
#define m 7
#define n 8
void path()
{
int maze[m+2][n+2] ;
int move[4][2]={ {0,-1},{-1,0},{0,1},{1,0} };
int s[54][3];
int top=0;
int i,j,k,f=0;
int g,h,p;
for(i=0;i
for(j=0;j
scanf("%d",&maze[i][j]);
maze[1][1]=2;
s[top][0]=1;
s[top][1]=1;
s[top][2]=0;
++top;
while(top!=0&&f==0)
{
--top;
i=s[top][0];
j=s[top][1];
k=s[top][2];
while(k
{
g=i+move[k][0];
h=j+move[k][1];
if(g==m&&h==n&&maze[g][h]==0) {
for(p=0;p
printf("%3d,%d\n",s[p][0],s[p][1]); printf("%3d,%d\n",i,j);
printf("%3d,%d\n",m,n);
f=1;
}//if
if(maze[g][h]==0)
{
maze[g][h]=2;
s[top][0]=i;
s[top][1]=j;
s[top][2]=k;
++top;
i=g;
j=h;
k=0;
}//if
k=k+1;
}//while
}//while
if(f==0)
printf("no path\n"); }//path
void main() {
path();
}