离散数学 实验报告 迷宫最短路径问题求解

离散数学迷宫问题

问题描述：

一只老鼠走进了一个迷宫，这个迷宫是由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<stdio.h>

#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<m+2;++i)

for(j=0;j<n+2;++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<4)

{

g=i+move[k][0];

h=j+move[k][1];

if(g==m&&h==n&&maze[g][h]==0) {

for(p=0;p<top;++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();

}