实验报告
课程名：数据结构（C语言版）实验名：迷宫问题I
姓名：
班级：
学号：
撰写时间：2014/10/05
一实验目的与要求
1. 了解栈的应用
2. 利用栈在迷宫中找到一条路
二实验内容
•一个迷宫如图1所示, 是由若干个方格构成的一个矩形, 其中有唯一的一个入口(用标示), 有唯一的一个出口(用△标示). 图中深色的方格无法到达, 浅色的方格都是可以到达的. 每一次只能从当前方格前进到与当前方格有公共边的方格中(因此前进方向最多有四个).
•本次实验的迷宫问题要求求解一条从入口到出口的路.
图1：迷宫
三实验结果与分析
程序：
#include <stdio.h>
#include <stdlib.h>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
int Maze(int ox,int oy,int ex,int ey,int rnum,int cnum,int a[rnum][cnum]){
int b[rnum][cnum];
int i,j,Znum=0;
for(i=0;i<rnum;++i){
for(j=0;j<cnum;++j){
b[i][j]=a[i][j];
if(a[i][j]==0){
Znum=Znum+1;
}
}
}
int Sx[Znum+1], Sy[Znum+1], p=0;
for(i=0;i<Znum+1;++i){
Sx[i]=-1;
Sy[i]=-1;
}
int dx[4] = {0,1,0,-1};
int dy[4] = {-1,0,1,0};
Sx[p]=ox;
Sy[p]=oy;
b[ox][oy]=2;
p=1;
int brand = -1;
//------------------------------------- while(p>0){
if(Sx[p-1]==ex && Sy[p-1]==ey){
brand = 1;
break;
}
else{
int tb = -1;
for(i=1;i<4;++i){
int tx = Sx[p-1]+dx[i];
int ty = Sy[p-1]+dy[i];
if(b[tx][ty]==0){
tb = 1;
Sx[p]=tx;
Sy[p]=ty;
b[tx][ty]=2;
p=p+1;
}
}
if(tb<0){
b[Sx[p-1]][Sy[p-1]]=-1;
p=p-1;
}
}
}
if(brand>0){
while(p>0){
printf("(%d,%d), ",Sx[p-1],Sy[p-1]);
p=p-1;
}
}
return(brand);
}
int main(int argc, char *argv[]) {
int rnum = 10; //rnum和cnum分别对应行和列
int cnum = 10;
int a[10][10]={{1,1,1,1,1,1,1,1,1,1},
{1,0,0,1,0,0,0,1,0,1},
{1,0,0,1,0,0,0,1,0,1},
{1,0,0,0,0,1,1,0,0,1},
{1,0,1,1,1,0,0,0,0,1},
{1,0,0,0,1,0,0,0,0,1},
{1,0,1,0,0,0,1,0,0,1},
{1,0,1,1,1,0,1,1,0,1},
{1,1,0,0,0,0,0,0,0,1},
{1,1,1,1,1,1,1,1,1,1}};
//假设迷宫外围有一层不可到达的方块，则方块变成了10X10 int ox=1,oy=1,ex=rnum-2,ey=cnum-2;
int brand = Maze(ox,oy,ex,ey,rnum,cnum,a);
if(brand<0){
printf("There is no way\n");
}
return 0;
}
图1：实验结果截图。