数据结构课程设计报告 迷宫问题

吉林大学软件学院课程设计报告

课程名称： 数据结构课程设计

课程题目： 迷宫问题 姓名： *** 学号： ********

软件学院2009级《数据结构》课程设计

题目一: 迷宫问题

[实验目的]

综合运用数组、递归等数据结构知识，掌握、提高分析、设计、实现及测试程序的综合能力。

[实验内容及要求]

以一个M×N的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。

（1） 根据二维数组，输出迷宫的图形。

（2） 探索迷宫的四个方向：RIGHT为向右，DOWN向下，LEFT向左，UP向

上，输出从入口到出口的行走路径。 [测试数据]

左上角（1，1）为入口，右下角（8，9）为出口。

0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 1 0 1 1 1 1 1 1 1 0 0 1 0 0 0 0 1 1 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 1 0 1 0 1 0 1 0 0 0 0 0 0 1 0 0 1 1 1 0

[实现方法]

可使用回溯方法，即从入口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。

[具体思路及结果]

首先，事先声明好矩阵，矩阵长宽，栈顶元素，矩阵点左边等。

然后，要求用户尽享交互输入迷宫(maze)各个点处的值(1或0) 保存并初始化栈顶元素，置所有方向数为下。

之后，一比较整洁大方的形式打印原迷宫供用户查看。

同时，开始本程序的重点，回溯算法，以1,2,3,4分别表示下上左右。

多次使用for循环寻找可以到达出口的路径，期间分别先后试探下，左，上，右 置已经走过的点为2防止死循环，寻找完后存在TOP[]栈中。

最后，打印找到的当前迷宫路径并以（坐标1）——>（坐标2）的形式输出路径，并且在原迷宫的基础上表示出当前找到的路径，以#代表走过的路径0代表没有障碍的地方，1代表障碍，画出迷宫路径图，并且立刻执行下一次循环，寻找下一条可通过的路径，并还原迷宫图，继续寻找路径知道找到所有解后自动退出。

[具体代码]

#include #include #define n1 5 #define n2 5

typedef struct node { int x;//存x坐标 int y;//存y坐标 int c;//存该点可能的下点所在的方向，表示向1表示向下，2左，3向上，4向右 }linkstack;

linkstack top[25];

int rows=0; int cols=0;

int i,j,k,m,p,q=0; int maze[n1][n2];

void main() { for(p=0;p<=n1-1;p++){ for(q=0;q<=n2-1;q++){ printf(\"请输入第%d行第%d列的数\\n\ scanf(\"%d\ } } //初始化top[]，置所有方向为下 for(i=0;i //打印原迷宫 for(i=0;iprintf(maze[i][j]?\"1 \":\"0 \"); printf(\"\\n\");}

i=0;top[i].x=0;top[i].y=0; maze[0][0]=2; //回溯算法 do{ if(top[i].c<5) //还可以向前试探 {if(top[i].x==4&&top[i].y==4) //已找到一个组合 { //打印路径 printf(\"The way %d is:\\n\ for(j=0;j<=i;j++) {printf(\"(%d,%d)-->\ printf(\"\\n\"); //打印选出路径的迷宫 for(j=0;jtop[i].y=top[i-1].y; maze[top[i].x][top[i].y]=2;} else {top[i].c+=1;} break;} case 3: {if(maze[top[i].x][top[i].y-1]==0)//上 {i++; top[i].x=top[i-1].x; top[i].y=top[i-1].y-1; maze[top[i].x][top[i].y]==2;} else {top[i].c+=1;} break;} case 4: {if(maze[top[i].x+1][top[i].y]==0)//右 {i++; top[i].x=top[i-1].x+1; top[i].y=top[i-1].y; maze[top[i].x][top[i].y]=2;} else {top[i].c+=1;} break;} } } else //回溯 {if(i==0) return; //已找完所有解 maze[top[i].x][top[i].y]=0; top[i].c=1; i--; top[i].c+=1;} }while(1); }

[程序效果图]