/* 迷宫问题的非递归算法(栈实现)*/
#define MAXNUM 100/* 栈中最大元素个数 */
#define N 11 /*地图的第一维长度*/
#include <stdio.h>
#include <stdlib.h>
typedef struct {
int x;/* 行下标 */
int y;/* 列下标 */
int d;/* 运动方向 */
} DataType;
struct SeqStack { /* 顺序栈类型定义 */
int t; /* 指示栈顶位置 */
DataType s[MAXNUM];
};
typedef struct SeqStack *PSeqStack; /* 顺序栈类型的指针类型 */
PSeqStack pastack; /* pastack是指向顺序栈的一个指针变量 */
PSeqStack createEmptyStack_seq( void ) {
PSeqStack pastack;
pastack = (PSeqStack)malloc(sizeof(struct SeqStack));
if (pastack == NULL)
printf("Out of space!! \n");
else
pastack->t = -1;
return pastack;
}
int isEmptyStack_seq( PSeqStack pastack ) {
return pastack->t == -1;
}
/* 在栈中压入一元素x */
void push_seq( PSeqStack pastack, DataType x ) {
if( pastack->t >= MAXNUM - 1 )
printf( "Overflow! \n" );
else {
pastack->t++;
pastack->s[pastack->t] = x;
}
}
/* 删除栈顶元素 */
void pop_seq( PSeqStack pastack ) {
if (pastack->t == -1 )
printf( "Underflow!\n" );
else
pastack->t--;
}
/* 当pastack所指的栈不为空栈时,求栈顶元素的值 */
DataType top_seq( PSeqStack pastack ) {
return (pastack->s[pastack->t]);
}
void pushtostack(PSeqStack st, int x, int y, int d) {
DataType element;
element.x = x;
element.y = y;
element.d = d;
push_seq(st, element);
}
void printpath(PSeqStack st) {
DataType element;
printf("The revers path is:\n"); /* 打印路径上的每一点 */
while(!isEmptyStack_seq(st)) {
element = top_seq(st);
pop_seq(st);
printf("the node is: %d %d \n", element.x, element.y);
}
}
/* 迷宫maze[M][N]中求从入口maze[x1][y1]到出口maze[x2][y2]的一条路径 */
/* 其中 1<=x1,x2<=M-2 , 1<=y1,y2<=N-2 */
void mazePath(int maze[][N], int direction[][2], int x1, int y1, int x2, int y2) {
int i, j, k, g, h;
PSeqStack st;
DataType element;
st = createEmptyStack_seq( );
maze[x1][y1] = 2; /* 从入口开始进入,作标记 */
pushtostack(st, x1, y1, -1); /* 入口点进栈 */
while ( !isEmptyStack_seq(st)) { /* 走不通时,一步步回退 */
element = top_seq(st);
pop_seq(st);
i = element.x; j = element.y;
for (k = element.d + 1; k <= 3; k++) { /* 依次试探每个方向 */
g = i + direction[k][0];h = j + direction[k][1];
if (g == x2 && h == y2 && maze[g][h] == 0) { /* 走到出口点 */
printpath(st); /* 打印路径 */
return;
}
if (maze[g][h] == 0) { /* 走到没走过的点 */
maze[g][h] = 2; /* 作标记 */
pushtostack(st, i, j, k); /* 进栈 */
i = g; j = h; k = -1; /* 下一点转换成当前点 */
}
}
}
printf("The path has not been found.\n");/* 栈退完未找到路径 */
}
int main(){
int direction[][2]={0,1,1,0,0,-1,-1,0};
int maze[][N] = {
1,1,1,1,1,1,1,1,1,1,1,
1,0,1,0,0,1,1,1,0,0,1,
1,0,0,0,0,0,1,0,0,1,1,
1,0,1,1,1,0,0,0,1,1,1,
1,0,0,0,1,0,1,1,0,1,1,
1,1,0,0,1,0,1,1,0,0,1,
1,1,1,0,0,0,0,0,0,0,1,
1,1,1,1,1,1,1,1,1,1,1
};
mazePath(maze,direction,1,1,6,9);
getchar();
return 0;
}
迷宫问题解决方法集锦
需积分: 0 104 浏览量
2009-01-01
11:28:42
上传
评论
收藏 14KB RAR 举报
ben202
- 粉丝: 0
- 资源: 7
最新资源
- 206693250008_R01C02_Grn.idat
- 瞳孔跟踪-基于OpenCV+网络摄像头的瞳孔跟踪算法实现-附项目源码+流程教程-优质项目分享.zip
- ModStartCMS v8.4.0 框架稳定性持续迭代,修复部分已知问题
- bleder 教室学校学生教育室办公室考试
- 人脸检测-使用OpenCV实现的动漫+漫画人脸检测算法-附项目源码-优质项目实战.zip
- 道路贴图,材质材料免费
- 人脸检测-基于OpenCV+Node.js+WebSockets实现的实时人脸检测应用-附项目源码-优质项目实战.zip
- 一些常见的MySQL死锁案例-mysql-deadlocks-master(源代码+案例+图解说明)
- UE4动画烘焙器-ue4.27
- 新建文件夹.zip
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
评论0