#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
int m,n;
int **maze = NULL; //表示迷宫
struct Element{ //这里就是定义节点
int i;
int j;
int di;
};
typedef struct LinkStack { //这里就是定义链栈...
struct Element element;
struct LinkStack * next;
struct LinkStack * prior;
}LinkStack;
LinkStack *top = NULL; //栈顶指针,因为是链栈,所以栈顶指针要是一个指针变量
LinkStack *head = NULL; //链栈的头指针
int count=1; //路径计数
void printMaze(int ** maze) //输出迷宫
{
int i,j;
printf("您确定的迷宫图如下所示:\n");
for(i=0; i<m+2; i++) {
for(j=0; j<n+2; j++) {
printf("%4d",maze[i][j]);
}
printf("\n");
}
}
void addWall(int ** maze) //给迷宫加墙
{
int i,j;
for(i=0; i<m+2; i++)
{
for(j=0; j<n+2; j++) {
if(i==0){
maze[i][j] = 1;
}
if(i>0 && i<(m+2-1)) {
maze[i][0]=1;
maze[i][n+2-1]=1;
break;
}
if(i==m+2-1) {
maze[i][j]=1;
}
}
}
}
int ** initMaze() { //对迷宫进行初始化的函数
int i,j;
int flag = 0;
printf("请输入迷宫的行数 m=");
scanf("%d",&m);
printf("请输入迷宫的列数 n=");
scanf("%d",&n);
//是在给maze分配内存的时候有点点问题
maze = (int **)malloc(sizeof(int *) * (m+2)); //开辟迷宫的存储空间
for(i=0; i<n+2; i++)
{
*(maze+i) = (int *)malloc(sizeof(int)*(n+2));
}
addWall(maze); //给迷宫加墙
printf("\n请输入迷宫的各行各列(注意:最后一个数需要是0):\n用空格隔开,0代表路,1代表墙\n"); //保证出口是路,所以最后一个数要是0
for(i=1;i<=m;i++) {
for(j=1;j<=n;j++) {
scanf("%d",&maze[i][j]);
}
}
printf("你输完了\n");
printMaze(maze); //输出迷宫图
return maze;
}
void mazePath() {
if(top == head && head != NULL) //终止递归的条件
{
return;
}
int k = 0;
int find = 0;
int i = 0,j=0;
int di = -1;
if(top != NULL)di=top->element.di; //di一开始就保存当前栈顶指针所指的节点的方向
LinkStack *node= (LinkStack *) malloc(sizeof(LinkStack)); //每一次递归都首先开辟节点(因为要查找元素,所以要先开辟节点)
node->element.di = di;
if(top == NULL)
{
head = (LinkStack *) malloc(sizeof(LinkStack)); //链表的头指针
head->element.i = 1;
head->element.j = 0;
head->element.di = 1;
head->prior = NULL;
top = head;
node->element.i = 1;
node->element.j = 1;
node->element.di = -1;
}
top->next = node;
node->next = NULL;
node->prior = top;
top = node;
di = top->element.di;//取得当前栈顶指针所指的元素的方向
while(di<4 && find == 0)
{
di++;
switch(di)
{
case 0: i = top->prior->element.i - 1;j = top->prior->element.j;break;
case 1: i = top->prior->element.i;j = top->prior->element.j + 1;break;
case 2: i = top->prior->element.i + 1;j = top->prior->element.j;break;
case 3: i = top->prior->element.i;j = top->prior->element.j - 1;break;
}
if(maze[i][j] == 0)find = 1;
}
if(i == m && j == n)
{
top->element.i = m;
top->element.j = n;
top->prior->element.di = di;
printf("%4d:",count++);
LinkStack * n = head->next;
while(n != NULL)
{
printf("(%d,%d) ",n->element.i,n->element.j); //找到出口,输出路径
if((k + 1)%5 == 0)
{
printf("\n\t");
}
k++;
n = n->next;
}
printf("\n");
maze[top->element.i][top->element.j] = 0;
top = top->prior; //退栈
free(node);
mazePath();
}else {
if(find == 1)
{
top->prior->element.di = di;//退栈时,当找到下一个可走的节点后必须对当前节点的方向进行了更新
top->element.i = i;
top->element.j = j;
top->element.di = -1;
maze[i][j] = -1; //避免重复走到该点
mazePath();
}
else
{
maze[top->prior->element.i][top->prior->element.j] = 0;//让它成为下条路径的可走路径
top = top->prior->prior; //退栈
free(node);
mazePath();
}
}
}
void main() {
int i,j;
initMaze();
printf("您确定的迷宫图如下所示:\n");
printf("迷宫所有路径如下:\n");
mazePath();
if(maze != NULL) //释放开辟的所有内存空间
{
for(i=0;i<m+2;i++) //因为maze是二级指针,所以在释放maze所指的内存空间时,要先释放maze上的一级指针
{
free(maze[i]);
}
free(maze);
}
if(head != NULL) //释放内存
{
free(head);
}
return;
}
分享到:
相关推荐
使用随机Prim算法生成迷宫,Prim随机算法不是优先选择最近选中的单元格,而是随机的从所有的列表中的单元格进行选择,新加入的单元格和旧加入的单元格同样概率会被选择,新加入的单元格没有优先权。因此其分支更多,...
数据结构实验报告--链栈编写迷宫.doc
迷宫算法迷宫算法迷宫算法迷宫算法迷宫算法迷宫算法迷宫算法迷宫算法迷宫算法迷宫算法迷宫算法迷宫算法迷宫算法迷宫算法
使用栈解决老鼠迷宫问题 使用“拆墙”法生成迷宫 可以逐步演示,自动演示,用户控制 附带实验报告
迷宫算法迷宫算法迷宫算法迷宫算法迷宫算法迷宫算法迷宫算法迷宫算法
迷宫算法.rar 迷宫算法.rar 迷宫算法.rar
研究面向搜救的应用,将事故环境抽象为一个迷宫,通过仿真实验比较研究了深度优先搜索算法和三种不同启发式函数的A*算法在Perfect迷宫中的应用,并分别将深度优先搜索算法和A*算法用于实际迷宫中进行实现与比较。...
基于Python实现的迷宫求解小游戏.zip 这是95分以上高分必过课程设计项目,下载即用无需修改,确保可以运行。也可作为期末大作业。 基于Python实现的迷宫求解小游戏.zip 这是95分以上高分必过课程设计项目,下载即...
货郎担限界算法.txt 质因子.txt 输出自已.txt 迷宫.txt 迷宫问题.txt
作品:《最短迷宫寻路算法的演示》.rar
迷宫算法迷宫算法迷宫算法迷宫算法迷宫算法迷宫算法
【H5JS】游戏常用算法-路径搜索算法-随机迷宫算法(普里姆算法).pdf
数据结构经典,vc/c++,队列,迷宫算法
堆栈+数据结构 实现迷宫模拟算法
数据结构课程设计迷宫算法的实现-JAVA.doc
下载该资源前请确认已下载前置资源(随机迷宫生成算法),使用时先使用随即迷宫生成算法生成迷宫.txt文件,再将该文件复制到破解迷宫算法C文件同目录下才可使用。请确保头文件中的raw值和column值与随机迷宫生成算法...
基于Python实现的机器人自动走迷宫源码+文档报告.zip已获导师指导并通过的97分的高分大作业设计项目,可作为课程设计和期末大作业,下载即用无需修改,项目完整确保可以运行。 基于Python实现的机器人自动走迷宫...
这是我自己写的一个迷宫算法,可以运行,不过没有包括可以随机生成正确迷宫的算法。随机数生成的我自己测试还没出现过能走出迷宫的。
利用C语言实现迷宫算法。 利用随机函数生成迷宫,并显示所有路径.zip
数据结构课程设计迷宫算法的实现_JAVA.doc