博客分类：
#include &stdio.h&
#include &stdlib.h&
#define MAXSIZE 20
#define ERROR -1
#define OK
#define FALSE 0
#define TRUE
typedef enum{RIGHT,DOWN,LEFT,UP}D
typedef enum{YES,NO}MarkT
typedef struct position
//迷宫中位置的坐标
typedef struct
//当前位置在路径中的序号
//当前位置在迷宫中的坐标
//从当前位置走到下一位置的方向
//栈元素的类型
typedef struct
SElemType *
char maze[MAXSIZE][MAXSIZE]={
{'1','1','1','1','1','1','1','1','1','1'},
{'1','0','0','1','0','0','0','1','0','1'},
{'1','0','0','1','0','0','0','1','0','1'},
{'1','0','0','0','0','1','1','0','0','1'},
{'1','0','1','1','1','0','0','0','0','1'},
{'1','0','0','0','1','0','0','0','0','1'},
{'1','0','1','0','0','0','1','0','0','1'},
{'1','0','1','1','1','0','1','1','0','1'},
{'1','1','0','0','0','0','0','0','0','1'},
{'1','1','1','1','1','1','1','1','1','1'}
//用二维字符数组表示迷宫
int InitStack(Stack *S)
//创建一个空栈
S-&elem=(SElemType*)malloc(MAXSIZE*MAXSIZE*sizeof(SElemType));
if(!S-&elem)
return ERROR;
return OK;
int Push(Stack *S,SElemType e)
//元素e入栈
if(S-&top&=MAXSIZE*MAXSIZE)
return ERROR;
S-&elem[S-&top++]=e;return OK;
int Pop(Stack *S,SElemType *e) //栈顶元素出栈，由e带回栈顶元素
if(S-&top&=0)
return ERROR;
*e=S-&elem[--S-&top];
return OK;
int Empty(Stack S)
//判断栈是否为空
if(S.top==0)
return TRUE;
return FALSE;
int createMaze(Position *startpos,Position *endpos)
{ Position start,
printf("请输入迷宫入口的位置：");
scanf("%d%d",&start.x,&start.y);
printf("请输入迷宫出口的位置：");
scanf("%d%d",&end.x,&end.y);
*startpos= *endpos=
return OK;
//createMaze
int canPass(Position curpos)
if(maze[curpos.x][curpos.y]=='0')
return TRUE;
return FALSE;
void markPos(Position curpos,MarkTag tag)
//为已经探索过的位置加标记
switch(tag)
case YES: maze[curpos.x][curpos.y]='.';
//路径标记
maze[curpos.x][curpos.y]='#';
//死胡同标记
//根据当前的位置坐标和下一步要探索的方向dir求下一步要走的位置坐标
Position nextPos(Position curpos,Direction dir)
switch(dir)
case RIGHT:nextpos.x=curpos.nextpos.y =curpos.y +1;
case DOWN :nextpos.x=curpos.x+1 ;nextpos.y =curpos.y;
case LEFT :nextpos.x=curpos.nextpos.y =curpos.y -1;
case UP :nextpos.x=curpos.x-1 ;nextpos.y =curpos.y;
Direction nextDir(Direction dir)
switch(dir)
case RIGHT: return DOWN;
case DOWN : return LEFT;
case LEFT: return UP;
int Solve(Stack *S,Position start,Position end)
{//若迷宫中存在从入口start到出口end的通道，则求得一条存放在栈S中，并返回TRUE,若迷宫中不存在从入口start到出口end的通道，并返回FALSE
int curstep=1;
//共用的步数
if(InitStack(S)==ERROR)
return FALSE;
if(canPass(curpos)){
//当前位置可以通过
markPos(curpos,YES);
//留下足迹
e.order=e.seat=e.di=RIGHT;
Push(S,e);
//当前位置加入路径
if(curpos.x==end.x&&curpos.y==end.y)
//当前位置是出口
return TRUE;
curpos=nextPos(curpos,RIGHT);
curstep++;
//当前位置不能通过
if(!Empty(*S)){
if(Pop(S,&e)==ERROR)
return FALSE;
while(e.di==UP&&!Empty(*S)){
//四个方向都试探过，没有找到通路也不能继续探索，则回溯
curpos=e.markPos(curpos,NO);
if(Pop(S,&e)==ERROR)
return FALSE;
if(e.di!=UP){
//四个方向还没有试探完
e.di=nextDir(e.di);
Push(S,e);
//换下一个方向探索
curpos=nextPos(e.seat,e.di);
}while(!Empty(*S));
return FALSE;
void main()
Position startPos,endP
if(createMaze(&startPos,&endPos)==ERROR)
Solve(&path,startPos,endPos);
while(!Empty(path)){
//输出出口到入口的路径
Pop(&path,&e);
printf("(%d,%d)",e.seat.x,e.seat.y);
//输出迷宫的图形
printf("\n");
for(i=0;i&10;i++)
{for(j=0;j&10;j++)
printf("%c ",maze[i][j]);
printf("\n");
本文来源：
浏览: 2854 次
(window.slotbydup=window.slotbydup || []).push({
id: '4773203',
container: s,
size: '200,200',
display: 'inlay-fix'C语言使用深度优先搜索算法解决迷宫问题(堆栈)
转载 & & 作者：e
这篇文章主要介绍了C语言使用深度优先搜索算法解决迷宫问题,涉及C语言堆栈的使用与深度优先算法解决迷宫问题的相关操作技巧,需要的朋友可以参考下
本文实例讲述了C语言使用深度优先搜索算法解决迷宫问题。分享给大家供大家参考，具体如下：
深度优先搜索
（Pseudocode）如下：
将起点标记为已走过并压栈;
while (栈非空) {
从栈顶弹出一个点p;
if (p这个点是终点)
否则沿右、下、左、上四个方向探索相邻的点
if (和p相邻的点有路可走，并且还没走过)
将相邻的点标记为已走过并压栈，它的前趋就是p点;
if (p点是终点) {
打印p点的坐标;
while (p点有前趋) {
p点 = p点的前趋;
打印p点的坐标;
没有路线可以到达终点;
C语言代码：
#include &stdio.h&
#define MAX_ROW 5
#define MAX_COL 5
struct point { int row, } stack[512];
int top = 0;
void push(struct point p)
stack[top++] =
struct point pop(void)
return stack[--top];
int is_empty(void)
return top == 0;
int maze[MAX_ROW][MAX_COL] = {
0, 1, 0, 0, 0,
0, 1, 0, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
void print_maze(void)
for (i = 0; i & MAX_ROW; i++) {
for (j = 0; j & MAX_COL; j++)
printf("%d ", maze[i][j]);
putchar('\n');
printf("*********\n");
struct point predecessor[MAX_ROW][MAX_COL] = {
{{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}},
{{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}},
{{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}},
{{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}},
{{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}},
void visit(int row, int col, struct point pre)
struct point visit_point = { row, col };
maze[row][col] = 2;
predecessor[row][col] =
push(visit_point);
int main(void)
struct point p = { 0, 0 };
maze[p.row][p.col] = 2;
while (!is_empty()) {
p = pop();
if (p.row == MAX_ROW - 1 /* goal */
&& p.col == MAX_COL - 1)
if (p.col+1 & MAX_COL /* right */
&& maze[p.row][p.col+1] == 0)
visit(p.row, p.col+1, p);
if (p.row+1 & MAX_ROW /* down */ && maze[p.row+1][p.col] == 0)
visit(p.row+1, p.col, p);
if (p.col-1 &= 0 /* left */ && maze[p.row][p.col-1] == 0)
visit(p.row, p.col-1, p);
if (p.row-1 &= 0 /* up */
&& maze[p.row-1][p.col] == 0)
visit(p.row-1, p.col, p);
print_maze();
if (p.row == MAX_ROW - 1 && p.col == MAX_COL - 1)
printf("(%d, %d)\n", p.row, p.col);
while (predecessor[p.row][p.col].row != -1) {
p = predecessor[p.row][p.col];
printf("(%d, %d)\n", p.row,
printf("No path!\n");
希望本文所述对大家C语言程序设计有所帮助。
您可能感兴趣的文章:
大家感兴趣的内容
12345678910
最近更新的内容
常用在线小工具【迷宫问题】用堆栈解迷宫_百度知道
【迷宫问题】用堆栈解迷宫
我们c语言实践课的题目，我实在编不出来，求助。。
题目：有一个40*60的迷宫，0和1分别表示迷宫中的通路和障碍，设计一个程序,对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。
对于本问题需用栈实现“穷举求解”算法，即：从入口出发...
我有更好的答案
//&{&&&&&&&&line_len&=&i;&4个方向void&&i&&&4;&i++)&&&&{&&0;&&MAXN&&&&0;&-1,&0&|&y;&&&&&&&&&&&&dfs(x,&y,&step+1);&&&&&&&&&&&&//&used[x][y]&=&&y&=&1;&nbsp,&&&&60;&//&40行60列int&};&&&&&&u&+&=&0&y;x&=&&==&nbsp,&1&},&{&for&(i&=&nbsp,&(u&dfs(int&u,&int&随机生成迷宫&maze[x][y]==0)&&&d[i][0];16&for&(i&=&0;&i&&&m;&i++)&&&&&&&&for&(j&=&0;&j&&&n;&j++)&&&&&&&&&&&&maze[i][j]&=&rand()%8&==&0&?&1&:&0;&//&是1的概率约1/8,通路的概率大些&&&&maze[0][0]&=&maze[m-1][n-1]&=&0;&//&起始点和终端必须为0&&&&line_len&=&0;&&&&line[0]&=&0&&&&16&|&0;&&&&memset(used,&0,&sizeof(used));&&&&dfs(0,&0,&0);&//&(0,0)&-&&(m-1,&n-1)&&&&if&(line_len&==&0)&&&&&&&&printf(&没有通路\n&);&&&&else&&&&{&&&&&&&&for&(i&=&0;&i&&&line_&i++)&&&&&&&&&&&&printf(&(&%d,&%d&)\n&,&(line_r[i]&&16)+1,&(line_r[i]&0xffff)+1);&&&&}&&&&return&0;}&你给的那库实在是没什么用的欲望，要最短路径一般用广度搜索，上面的代码应该属于深度搜索;0;&m-1&&n&&&main()&//&&if&&nbsp,&&srand(time(NULL));1;&&&d[4][2]&=&&nbsp,&&stdlib.h&gt,&if&&&y&&j;if&int&line_r[MAXM*MAXN];int&string.h&&y&&=&&0&1-障碍物int&m&&&&&&&}&&{&&&&int&&nbsp,&&&&&&&&//&&nbsp!used[x][y]&&&&=&40;&&v&x&&&m&&&&&&0&},&{&//&&v&+&&&&&&&&&&&&memcpy(line_r,&不用退回来了，因为只需要一条路径&&&n&=&i;&60int&maze[MAXM][MAXN]!=&0)&&&&&&&&&=&x&&x;n-1)&&&&#include&&&记录迷宫路线int&line_//&(line_len&,&line[step]&&&&&time.h&&d[i][1];&&&&{&&&&&&&&&&&&used[x][y]&=&0&&#define&MAXM&40&&#define&}&&&&}}int&&{&{&int&step){&&&&int&&&&&;&#include&&nbsp#include&&stdio.h&&&{&0,&-1}&&&line[MAXM*MAXN];&lt,&&(x&&&&&&&&used[MAXM][MAXN];&//&记录是否到过int&&&&&line_len*sizeof(int));&#include&};&&v;==&&nbsp
那个库不能用吗。。据说好像只会用到push和pop什么的。。迷宫也是他做好的txt文件，用二进制读入到二维数组就行。。我真是太渣了你写的有点看不懂QAQ我们要跟老师解释程序的、不用那个库看着不像自己写的说~&_&~
库里面的内容用处不大，封装成一堆无用函数（说的直白了点，勿怪）要用是替换代码里的line数组，存储结果用的
采纳率：38%
为您推荐：
其他类似问题
堆栈的相关知识
换一换
回答问题，赢新手礼包
个人、企业类
违法有害信息,请在下方选择后提交
色情、暴力
我们会通过消息、邮箱等方式尽快将举报结果通知您。他的最新文章
他的热门文章
您举报文章：
举报原因：
原文地址：
原因补充：
(最多只允许输入30个字)迷宫问题的代码
在电子工程世界为您找到如下关于“迷宫问题的代码”的新闻
迷宫问题的代码资料下载
迷宫问题的代码，能用哟，给那些需要的人使用，并欢迎大家讨论研究...
迷宫问题的vc源代码，带地图编辑功能，可以自己设计地图,可能不算很经典,但是也是值得学习的...
2.2 栈的应用与递归
2.2.1 数制转换
2.2.2 表达式求值
2.2.3 汉诺塔问题与递归的实现
2.2.4 迷宫问题
2.2.5 皇后问题
2.2.6 马踏棋盘问题
2.2.7 背包问题
2.3.1 队列的链式存储结构
2.3.2 队列的顺序存储结构
2.4 队列的应用——排队和排队机的模拟
数据结构课程设计报告及代码 C语言环境 迷宫问题的设计...
迷宫问题的代码相关帖子
迷宫问题的代码视频
你可能感兴趣的标签
热门资源推荐