迷宫问题的C,C算法实现讲解

1、基于栈的 C 语言迷宫问题与实现一 问题描述多年以来， 迷宫问题一直是令人感兴趣的题目。 实验心理学家训练老鼠在迷宫中寻找食物。 许多神秘主义小说家也曾经把英国乡村花园迷宫作为谋杀现场。于是， 老鼠过迷宫问题就此产生，这是一个很有趣的计算机问题，主要利用 “栈”是老鼠通过尝试的办法从入口穿过 迷宫走到出口。迷宫只有两个门， 一个叫做入口， 另一个叫做出口。 把一只老鼠从一个无顶盖的大盒子的 入口处赶进迷宫。 迷宫中设置很多隔壁， 对前进方向形成了多处障碍， 在迷宫的唯一出口处 放置了一块奶酪， 吸引老鼠在迷宫中寻找通路以到达出口。 求解迷宫问题， 即找出从入口到 出口的路径。一个迷宫可用上图所

2、示方阵 m,n表示， 0 表示能通过， 1 表示不能通过。现假设耗子从 左上角 1,1进入迷宫，编写算法，寻求一条从右下角 m,n 出去的路径。下图是一个迷宫的 示意图：二 算法基本思想迷宫求解问题是栈的一个典型应用。 基本算法思想是：在某个点上，按照一定的顺序（在本 程序中顺序为上、右、下、左）对周围的墙、路进行判断（在本程序中分别用1、0）代替，若周围某个位置为 0，则移动到该点上，再进行下一次判断；若周围的位置都为 1（即没有 通路），则一步步原路返回并判断有无其他通路，然后再次进行相同的判断，直到走到终点 为止，或者确认没有任何通路后终止程序。要实现上述算法，需要用到栈的思想。栈里面压

3、的是走过的路径， 若遇到死路，则将该位置 （在栈的顶层） 弹出， 再进行下一次判断； 若遇到通路， 则将该位置压栈并进行下一次判断。 如此反复循环， 直到程序结束。 此时，若迷宫有通路，则栈中存储的是迷宫通路坐标的倒序 排列，再把所有坐标顺序打印后，即可得到正确的迷宫通路。程序具体部分的说明1.迷宫的生成 根据题目的要求，迷宫的大小是自定义输入的。所以在程序中用 malloc 申请动态二 维数组。数组中的元素为随机生成的0 、1。数组周围一圈的元素全部定义为 1，以表示边界。2.栈的 C 语言实现 为了实现栈的功能，即清空、压栈、弹出、返回栈顶元素，在程序中编写了相应的 函数。MakeNULL

4、 清空栈Push 将横、纵坐标压栈Topx 返回栈顶存储的横坐标Topy 返回栈顶存储的纵坐标Pop 弹出栈顶元素3.具体的判断算法当位置坐标（程序中为 X Y）移到某一位置时，将这个位置的值赋值为1 并压栈，以说明该点已经走过。接着依次判断该点的上、右、下、左是否为0，若有一方为 0，则移动到该位置上，进行下次判断；若为周围位置全部是1，则将该点压栈后不断弹出，每次弹出时判断栈顶元素（即走过的路）周围有无其他通路。如果有的话， 则选择该方向继续走下去；如果栈已经为空仍然没有找到出路，则迷宫没有出口程 序结束。当 X Y 走到出口坐标时，程序判断部分结束。栈里面存储的是每个走过的点的坐标， 将

5、这些横纵坐标分别存储在两个数组中，最后将数组中的坐标元素倒序输出，即得 到了完整的路径。四 程序源代码及注释/ Maze.cpp : 定义控制台应用程序的入口点。/#include "stdafx.h"#include <stdio.h>#include <string.h>#include <malloc.h>#include <stdlib.h>#include <time.h> typedef int Elementtype; struct nodeElementtype val1;Elementtype v

6、al2;node *next; / 定义结构体typedef node *MAZE; void MakeNull(MAZE &S); void Push(Elementtype x,Elementtype y, MAZE S); void Pop(MAZE S);Elementtype Topx(MAZE S);Elementtype Topy(MAZE S); / 申明函数 int _tmain( int argc, _TCHAR* argv) int *p,*q,*x1,*y1,i,j,k,n1,n2,m1,m2,l,w,max; int x,y;int a,b,c,d;print

7、f("输入迷宫长度及宽度 l 和wn" );scanf( "%d %d",&l,&w);getchar();n1=w+2;n2=l+2; / 为迷宫加上边界max=n1*n2;p=( int *)malloc(n1* sizeof (int );for (i=0;i<n1;i+)pi=( int *)malloc(n2* sizeof (int ); / 生成二维动态数组 srand(time(NULL);x1=( int *)malloc(max* sizeof (int ); / 生成动态数组用于存储路径 y1=( int *)

8、malloc(max* sizeof (int ); / 生成动态数组用于存储路径 for (i=0;i<max;i+)x1i=0;for (i=0;i<max;i+)y1i=0;/ 先将存储路径的数组元素全赋值为 0for (i=0;i<n1;i+)for (j=0;j<n2;j+)if (i=0 | j=0)pij=1;else if (i=n1-1 | j=n2-1)pij=1;elsepij=rand()%2+0;/ 生成二维1 0随机数组p11=0;pn1-2n2-2=0; / 定义迷宫的入口及出口printf(" 生成的迷宫如下(代表墙 0代表路)

9、： n" );for (i=0;i<n1;i+)for (j=0;j<n2;j+)printf( "%2d",pij); printf( "n" );/ 打印迷宫MAZE S;MakeNull(S); / 清空栈i=1;j=1;if (p12=1 && p21=1)printf( "There is no way out" );a getchar();return 0;/ 判断入口是否就是死路 else doif (pi-1j=0) x=i; y=j;Push(x,y,S); pij=1;i=i-

10、1; / 判断能否向上走else if (pi-1j=1 && pij+1=0) x=i;y=j; Push(x,y,S);pij=1; j=j+1; / 判断能否向右走else if (pi-1j=1 && pij+1=1 && pi+1j=0) x=i;y=j; Push(x,y,S);k=Topx(S); pij=1; i=i+1; / 判断能否向下走else if (pi-1j=1 && pij+1=1 && pi+1j=1 && pij-1=0)x=i;y=j;Push(x,y,S);pi

11、j=1;j=j-1; / 判断能否向左走else if (pi-1j=1 && pij+1=1 && pi+1j=1 && pij-1=1) / 判断如果为死路pij=1;x=i;y=j;Push(x,y,S);for (;)Pop(S); / 弹出栈顶元素x=Topx(S);y=Topy(S); / 返回栈顶元素横纵坐标if ( px-1y=0)i=x-1;j=y;pij=1;x=i;y=j;Push(x,y,S); break ;else if (px-1y=1 && pxy+1=0)i=x;j=y+1;pij=1;x=i;y

12、=j;Push(x,y,S); break ;else if (px-1y=1 && pxy+1=1 && px+1y=0)i=x+1;j=y;pij=1;x=i;y=j;Push(x,y,S);break ;else if (px-1y=1 && pxy+1=1 && px+1y=1 && pxy-1=0)i=x;j=y-1;pij=1;x=i;y=j;Push(x,y,S); break ; / 判断弹出后栈顶元素周围有无通路else if (x=1 && y=1)printf( "T

13、here is no way out" ); getchar();return 0; / 如果栈顶元素为入口则迷宫无出路 while (i!=n1-2 | j!=n2-2);/ 循环截止条件printf( "Success!n The route is:n");for (i=0;i+)a=Topx(S); b=Topy(S);Pop(S);x1i=a;y1i=b; / 将栈顶元素坐标存储在数组中if (a=1 && b=1)getchar();break ;for (i=max-1;i>=0;)if (x1i!=0 && (x

14、1i!=x1i-1 | y1i!=y1i-1)printf( "<%d ,%d> " ,x1i,y1i);i-;else if (x1i!=0 && (x1i=x1i-1 && y1i=y1i-1) printf( "<%d ,%d> " ,x1i,y1i); i=i-2;elsei-;/ 倒序打印数组得到顺序出路坐标printf( "<%d ,%d>",n1-2,n2-2); / 打印出口坐标 getchar();return 0;void MakeNull(MAZ

15、E &S) / 清空栈的函数S = new node;S->next = NULL;/ 压栈函数void Push(Elementtype x,Elementtype y, MAZE S) MAZE stk;stk = new node; stk->val1 = x; stk->val2 = y; stk->next = S->next; S->next = stk;void Pop(MAZE S)/ 弹出函数MAZE stk;if (S->next)stk = S->next;S->next = stk->next; del

16、ete stk;Elementtype Topx(MAZE S) / 返回横坐标函数 if (S->next)return (S->next->val1);elsereturn NULL;Elementtype Topy(MAZE S) / 返回纵坐标函数 if (S->next)return (S->next->val2);elsereturn NULL;另一种方法实现的迷宫代码 #ifndef MMIGONG_H #define MMIGONG_H #define MAX_SIZE 100 #include<iostream> using n

17、amespace std;struct Nodeint x;int y;int di;class Stackprivate:int rrow;int ccolm;int top;int count;int minlenght;Node stackMAX_SIZE;Node sstackMAX_SIZE;public:Stack(); / 初始化/int *InsortMiGong();/输入迷宫 (即一个二维数组 )void FindPath(int ab10);/找出迷宫的出路;Stack:Stack() / 初始化rrow=0;ccolm=0;top=-1;count=1;minlengh

18、t=MAX_SIZE;/*int * Stack:InsortMiGong()/输入迷宫 (即一个二维数组 )int row=1,colm=1;while(true)cout<<" 请输入迷宫的行数和列数 :"cin>>row>>colm;if(row<=0|colm<=0)cout<<" 输入错误 !请重新输入 :"<<endl;rrow=row;ccolm=colm;continue;elserrow=row;ccolm=colm;break;int *mg;cout<&l

19、t;"请输入迷宫矩阵 (只有 0和 1两个数构成 ):"for(int i=0;i<row;i+)for(int j=0;j<colm;j+)cin>>mgij;return mg;*/void Stack:FindPath(int ab10) / 找出迷宫的出路int a,b,di,find,k;top+;stacktop.x=1;stacktop.y=1;stacktop.di=-1;ab11=-1;while(top>-1)a=stacktop.x;b=stacktop.y;di=stacktop.di;if(a=8&&b

20、=8)cout<<count+<<":"<<endl;for(int k=0;k<=top;k+) cout<<"("<<stackk.x<<","<<stackk.y<<")" if(!(k+1)%15) cout<<endl;cout<<endl;if(top+1<minlenght)for(k=0;k<=top;k+)sstackk=stackk; minlenght=to

21、p+1;abstacktop.xstacktop.y=0;top-;a=stacktop.x;b=stacktop.y;di=stacktop.di;find=0;while(di<8&&!find)di+; switch(di) case 0:a=stacktop.x-1;b=stacktop.y;break; case 1:a=stacktop.x;b=stacktop.y+1;break; case 2:a=stacktop.x+1;b=stacktop.y;break; case 3:a=stacktop.x;b=stacktop.y-1;break; if(abab=0)find=1;if (find=1)stacktop.di=di;top+;stacktop.x=a; stacktop.y=b;stacktop.di=-1; abab=-1;else abstacktop.xstacktop.y=0; top-;cout<<endl;cou