C语言迷宫程序

一． 问题描述

多年以来，迷宫问题一直是令人感兴趣的题目.实验心理学家训练老鼠在迷宫中寻找食物.许多神秘主义小说家也曾经把英国乡村花园迷宫作为谋杀现场。于是，老鼠过迷宫问题就此产生,这是一个很有趣的计算机问题,主要利用 “栈”是老鼠通过尝试的办法从入口穿过迷宫走到出口。

迷宫只有两个门，一个叫做入口,另一个叫做出口。把一只老鼠从一个无顶盖的大盒子的入口处赶进迷宫.迷宫中设置很多隔壁，对前进方向形成了多处障碍，在迷宫的唯一出口处放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口。求解迷宫问题，即找出从入口到出口的路径.

一个迷宫可用上图所示方阵[m，n]表示,0表示能通过，1 表示不能通过。现假设耗子从左上角［1,1]进入迷宫，编写算法，寻求一条从右下角［m，n] 出去的路径。下图是一个迷宫的示意图：

入口出口迷宫示意图

二． 算法基本思想

迷宫问题是栈应用的一个典型例子。求解过程可采用回溯法.回溯法是一种不断试探且及时纠正错误的搜索方法。从入口出发,按某一方向向前探索，若能走通（未走过的），即某处可以到达，则到达新点，否则试探下一方向 ； 若所有的方向均没有通路，则沿原路返回前一点，换下一个方向再继续试探,直到所有可能的通路都探索到，或找到一条通路，或无路可走又返回到入口点。

在求解过程中，为了保证在到达某一点后不能向前继续行走（无路）时，能正确返回前

一点以便继续从下一个方向向前试探，则需要用一个栈保存所能够到达的每一点的下标及从该点前进的方向，栈中保存的就是一条迷宫的通路。

为了确保程序能够终止,调整时，必须保证曾被放弃过的填数序列不被再次试验,即要求按某种有序模型生成填数序列.给解的候选者设定一个被检验的顺序,按这个顺序逐一生成候选者并检验。

三． 主要数据结构

1.方阵栈：

＃define STACK_INI_SIZE 100 typedef struct

｛

int ＊top； //指向栈的顶端域 int ＊base; //指向栈的低端域 int length; //栈的长度 int stacksize; //栈的最大长度 ｝sqstack；

2．产生迷宫的矩阵二维数组

为了使每一个迷宫存在迷宫的边界和两个端口：入口、出口，设置了一个二维数组，在迷宫的周边定义为1，使得迷宫存在边界，并在（1，1）,（x—2,y—2）初定义为0,即定义迷宫的出口,大大减小了无解的情况。 for（i=0;ifor（j=0；j〈y；j++)

mg[i][j］=rand（）%3;//产生随机数 i=0；

for（j=0;jmg[i]［j］=1； //定义边界 mg[j］[i］=1; ｝ i=y-1;

for(j=0;j//定义边界

for(j=0;j〈y;j++) mg［i］[j]=1； mg［1］［1］=0； mg[x-2]［y-2]=0;

//定义出口和入口

四． 主要函数功能

1． void initstack(sqstack ＊s）;/＊初始化栈*/

将栈顶和栈底分别申请一段动态存储空间,将栈分配长度为100的空间,将栈的原始长度定义为2

2． void stackpush(sqstack *s，int）；/＊增加栈顶＊/

将栈的动态存储空间增加50，将栈顶指针上移相应高度，特殊情况单独考虑见程序.

3． void stackpop（sqstack ＊s）;/＊撤销栈顶＊/ 栈空提示无法删除，其他情况删除栈顶.

4． void stackinput（sqstack ＊s);/*输出栈*/ 输出寻找到的一条迷宫路径

5． int mgway（sqstack *s）;/＊迷宫路径*/ 寻找到可执行的一条迷宫路径

6． void destorystack（sqstack ＊s)；/＊撤销栈S＊/ 将栈内元素清空

7． void makemg（sqstack *s）；/*制造迷宫＊/ 输入迷宫的长宽（2—15），并产生迷宫图

五． 算例（生成演算结果）

本程序的运算环境为：codeblocks 输入界面：

输入错误则重新输入

5*5的迷宫图及其路径：

继续输入错误提示：

重新输入结果：

可以看到每个迷宫都存在“围墙”

六． 分析算法 1. 空间复杂度

固定空间需求:25＊25的二维迷宫数组

可变空间需求：初始化栈中申请了100倍int型所占空间大小的动态空间，加入栈顶时额外申请50倍int型所占空间大小

2. 时间复杂度

可以通过“程序步”对程序的时间复杂度进行测量，可以引入count计数器进行测量，考虑到其复杂程度,本程序将不采用此方法。本程序的排错率较高，计算机会改掉没有通路的栈，并随机生成有通路迷宫,提高了程序的执行效率,并给迷宫添加了必要的围墙和出口、入口有助于执行效率的提高.但对于路径的搜索，栈并没有引入方向指针,在后面，通过flag进行标记来确定栈的路径的寻找的,一定程度上会影响执行效率.

附录：C语言源程序 ＃include #include〈stdlib.h>

#define STACK_INI_SIZE 100 ＃define STACKINCREMENT 50 #define NULL 0 typedef struct ｛

int ＊top； int ＊base; int length; int stacksize; }sqstack;

int mg[25］[25］; int m=1，n=1,x，y;

/＊*＊****＊*＊＊***＊＊******＊**＊＊＊*＊＊**＊*＊＊*＊*＊****/ main() {

void initstack（sqstack ＊s);/*初始化栈*/ void stackpush(sqstack ＊s,int）;/*增加栈顶*/ void stackpop(sqstack ＊s）;/*撤销栈顶*/ void stackinput（sqstack *s）；/＊输出栈＊/ int mgway(sqstack *s）;/＊迷宫路径*/

void destorystack(sqstack *s）;/*撤销栈S*/ void makemg(sqstack ＊s）；/＊制造迷宫＊/ sqstack s;

int i，flag1=1,flag2=1,flag3=1； char ch;

srand((unsigned)time（NULL）)； while（flag1) {

initstack（＆s）; flag2=1； makemg(&s）； i=mgway(&s)； if（i==0)

printf(”此迷宫没有通路\\n\"）; else

stackinput（&s)； destorystack（＆s）； printf（\"还继续么?”)； fflush（stdin）； scanf(”%c”，&ch）; while(flag2）

{

if(ch=='n’||ch=='N') ｛

flag1=0;

flag2=0； ｝

else if(ch==’y’｜|ch==’Y’) {

flag1=1； flag2=0; ｝ else {

printf（”输入错误请重新输入\")； fflush(stdin);

scanf(”％c\"，＆ch）; ｝ } } }

/*＊**＊＊**＊＊*****＊***＊＊*****＊＊＊*＊****＊＊*＊****＊*/ void initstack（sqstack *s)/*初始化栈*/ ｛

s—>top=s—〉base=(int *)malloc（STACK_INI_SIZE*sizeof（int））； if（！s->base) exit(1）；

s—>stacksize=STACK_INI_SIZE； ＊（s->base)=0; s->top++;

＊（s->top)=101； s-〉top++; s-〉length=2； ｝

/**＊＊**＊＊*＊****＊＊＊＊***＊*****＊****＊**＊＊****＊＊*＊/ void stackpush(sqstack ＊s,int i)/*增加栈顶＊/ ｛

if（s->length〉=s—>stacksize) ｛

printf(”路过\"）；

s—>base=(int ＊)realloc（s->base，(STACK_INI_SIZE+STACKINCREMENT）*sizeof(int））; if（!s->base） exit(1）;

s->top=s-〉base+s->length；

s-〉stacksize+=STACKINCREMENT； stackinput(s）； ｝

if（s-〉length==0) {

＊(s-〉base）=i； s-〉top++； s—〉length++; ｝ else {

＊(s—〉top)=i； s—〉top++; s—〉length++； ｝ }

/＊*＊*＊＊＊＊＊＊***＊*＊**＊＊*＊＊***＊＊*＊＊＊＊＊＊＊＊***＊＊*＊*/ void stackpop（sqstack ＊s)/＊删除栈顶＊/ {

if（s—>length==0)

printf（”栈空 无法删除”）； if(s—>length==1） ｛

s—>top--;

＊（s-〉top)=*（s—>base）=NULL; s->length=0； ｝ else ｛

s->top-—;

*（s—>top)=NULL; s->length——; } ｝

/*＊＊*＊*＊***＊*＊＊*＊＊＊＊**＊*＊**＊**＊＊*＊***＊＊*＊＊*＊*＊/ void stackinput(sqstack *s)/*迷宫栈的输出*/ {

int w，x,y，z,i=0，*p; p=s—〉base； p++；

printf(\"迷宫正确路径\\n\"）; while(p!=s—〉top） {

printf(”（%d%d，%d％d）\"，x=＊p/1000，y=＊p/100％10,z=＊p%100/10,w=＊p%10)；

p++; i++; if(i==7) ｛

printf(\"\\n\")； i=0; } } }

/＊**＊***＊*＊＊*＊＊**＊*＊＊＊*＊＊***＊＊＊******＊＊＊**＊**＊/ int mgway（sqstack *s)/*迷宫路径＊/ {

int gudge（sqstack *s，int）;/＊判断是否能通行*/ int homing(sqstack ＊s)；/＊退栈后I所对应的方向＊/ int i=1，j,k；

while（s—〉top！=s—〉base） {

if（i<5)

j=gudge(s，i)； if(j==1＆&i<5) {

k=m*100+n;

stackpush（s，k)； if（m==y-2＆&n==x-2） ｛

return(1）； ｝ else i=1； } else {

if(m==0＆&n==0) return(0）;

else if(i==4||i==5) ｛

i=homing（s); stackpop（s）; i++； ｝ else i++； }

｝

return(0); ｝

/*＊＊*＊＊＊****＊*＊＊*＊*＊*＊*＊＊**＊*＊*＊**＊＊＊*＊*＊**＊**/ int gudge(sqstack *s，int i）/＊退栈后i所对应的方向*/ {

int echo（sqstack ＊s); if（i==1） n++; if(i==2) m++; if(i==3) n-—;

if（i==4） m-—； if(（mg［m］［n]==0||mg[m][n］==2)＆&echo(s)) return（1); else {

if（i==1） n——； if(i==2） m--;

if（i==3） n++； if(i==4） m++； return（0）； } ｝

/*＊*＊＊**＊＊*＊＊*＊＊＊***＊****＊＊**＊*＊＊**＊＊＊**＊＊＊＊**/ int echo(sqstack *s） {

int i,＊p,*q； i=m*100+n;

p=s—〉top; q=s—〉base； q++; p——；

while(p!=q&&＊p！=i） p-—; if(*p==i)

return（0）； else

return(1）； ｝

/*＊*＊＊＊****＊＊＊*＊**＊＊＊＊＊＊＊***＊**＊＊＊＊*＊＊＊*＊**＊**/ int homing（sqstack ＊s)/*i退位后所对应的方向*/ ｛

int a,b,c，d,＊q; q=s—〉top； q——；

a=（＊q）/100； b=(*q)%100； q-—;

c=（*q）/100； d=（＊q)％100; m=(＊q）/100； n=(＊q）％100； if（a==c） {

if(d-b==1） return（3）; else if(d—b==—1) return(1）； }

else if(b==d） ｛

if（c—a==1) return（4）； else if（c-a==-1） return(2)； ｝

return（0)； }

void destorystack（sqstack ＊s） {

if(*(s—〉base）！=NULL) free(s->base);

s—〉length=0； ｝

/*＊**＊＊**＊＊*＊＊＊＊＊＊＊＊＊＊＊＊＊*＊**＊＊＊＊＊*＊＊**＊*＊*＊＊＊/ void makemg（sqstack *s）/*创建迷宫及输出迷宫图的函数＊/ {

int mgway(sqstack ＊s); void clearstack(sqstack ＊s); int flag=1,flag2=1,i，j,k; char ch;

while(flag)

｛

printf(\"请输入迷宫的长宽(长度范围2-15,宽范围2—15)\\n”）； printf(”输入长\"）； fflush（stdin)；

scanf（\"%d\"，＆y）; printf（\"输入宽”）; fflush（stdin）; scanf(”％d\"，&x)；

if(x〈16＆&x>3&＆y>3&&y<16) flag=0; if(flag==0）

printf(”自动筛选能通过的迷宫需要一段时间,请耐心等待,如20秒后无法显示出迷宫样本请重试..。 。.。\\n”）; }

flag=1;

while（flag2） {

m=1； n=1；

for（i=0;i〈x；i++) for（j=0；jmg［i］[j]=rand(）%3； i=0;

for（j=0；j〈y；j++) {

mg[i］[j］=1； mg［j]［i］=1； ｝

i=y—1；

for（j=0；jfor（j=0；jmg［x—2］[y—2]=0; k=mgway(s); if(k==1） flag2=0; else

clearstack(s); }

printf(\" ”);

for（i=0;i〈y；i++） printf(”％2d”，i）; printf（”\\n \"); for(i=0；iprintf(\"％2d→\）； for(j=0;j〈y;j++） {

if（mg［i］[j]==2） printf(\"0 ”); else

printf（\"%d \"，mg[i］［j]）； }

printf(\"\\n”）; } }

/＊＊***＊＊＊*＊***＊＊＊＊＊**＊＊*＊＊＊*＊＊＊＊**＊＊＊*＊＊****＊＊/ void clearstack(sqstack *s）/＊清空栈对于此程序而言*/ {

s—>top=s->base； *(s—〉base)=0; s—>top++;

*（s—>top）=101； s—>top++； s-〉length=2； ｝