数据结构递归做迷宫问题.doc

/*数据结构C语言版 递归求解迷宫问题用递归函数求解迷宫问题(求出所有解) 编译环境：Dev-C+ 4.9.9.2日期： 2011年2月12日*/#include/ 迷宫坐标位置类型struct PosType int x; / 行值 int y; / 列值 ;#define MAXLENGTH 25 / 设迷宫的最大行列为25 typedef int MazeTypeMAXLENGTHMAXLENGTH; / 行列 / 全局变量 struct PosType end;/ 迷宫终点位置 MazeType m;/ 迷宫数组 int x, y;/ 迷宫行数，列数 / 定义墙元素值为0,可通过路径为-1,通过路径为足迹 / 输出解void Print(int x,int y) int i,j;for(i=0;ix;i+)for(j=0;jy;j+)printf(%3d,mij);printf(n);printf(n);/ 由当前位置cur、当前步骤curstep试探下一点void Try(struct PosType cur,int curstep)int i;struct PosType next; / 下一个位置 / 行增量,列增量struct PosType direc4=0,1,1,0,0,-1,-1,0;/ 移动方向,依次为东南西北 for(i=0;i=3;i+) / 依次试探东南西北四个方向 next.x=cur.x+direci.x;next.y=cur.y+direci.y;if(mnext.xnext.y = -1) / 是通路 mnext.xnext.y=+curstep;if(next.x != end.x | next.y != end.y) / 没到终点 Try(next,curstep); / 试探下一点(递归调用) elsePrint(x,y); / 输出结果 mnext.xnext.y=-1; / 恢复为通路，试探下一条路 curstep-;/ 0为墙，-1为通道int main()struct PosType begin;/起点int i,j,x1,y1;printf(请输入迷宫的行数,列数(包括外墙)：（空格隔开）);scanf(%d%d,&x,&y);for(i=0;ix;i+) / 定义周边值为0(同墙) m0i=0;/ 迷宫上面行的周边即上边墙 mx-1i=0;/ 迷宫下面行的周边即下边墙 for(j=1;jy-1;j+)mj0=0;/ 迷宫左边列的周边即左边墙 mjy-1=0;/ 迷宫右边列的周边即右边墙 for(i=1;ix-1;i+)for(j=1;jy-1;j+)mij=-1; / 定义通道初值为-1 printf(请输入迷宫内墙单元数(即墙的个数)：);scanf(%d,&j);if(j)printf(请依次输入迷宫内墙每个单元的行数,列数：（空格隔开）n);for(i=1;i=j;i+)scanf(%d%d,&x1,&y1);mx1y1=0;printf(迷宫结构如下:n);Print(x,y);printf(请输入起点的行数,列数：（空格隔开）);scanf(%d%d,&begin.x,&begin.y);printf(请输入终点的行数,列数：（空格隔开）);scanf(%d%d,&end.x,&end.y);mbegin.xbegin.y=1;Try(begin,1); / 由第一步起点试探起 system(pause);return 0; /*输出效果：请输入迷宫的行数,列数(包括外墙)：（空格隔开）4 4请输入迷宫内墙单元数(即墙的个数)：1请依次输入迷宫内墙每个单元的行数,列数：（空格隔开）1 2迷宫结构如下: 0 0 0 0 0 -1 0 0 0 -1 -1 0 0 0 0 0请输入起点