c语言代码:C语言迷宫问题解决方法及代码

下面问题是个C语言迷宫问题解决思路方法及代码有兴趣可以研究下多多研究别人代码能提高自己水平
【问题描述】
以个m*n长方阵表示迷宫0和1分别表示迷宫中通路和障碍设计个对任意设定迷宫求出条从入口到出口通路或得出没有通路结论
【基本要求】

【测试数据】

【实现提示】
使用穷举法和栈求解
【代码过程】
1
//base.h
//-------------------公用常量和类型----------------------------
#<stdio.h>
#<malloc.h>
#<stdlib.h>
#<.h>
//结果状态代码
#TRUE1
#FALSE0
#OK1
#ERROR0
#INFEASIBLE-1
#OVERFLOW-2

typedefStatus;//返回值
typedefDirectiveType;//下个通道方向

#RANGE100//迷宫大小

//~

2

//stack.h
#STACK_INIT_SIZE100
#STACKINCREMENT10

//------------栈顺序存储实现------------------------------
typedefstruct...{
row;
col;
}PosType;

typedefstruct...{
step;//当前位置在路径上\"序号\"
PosTypeseat;//当前坐标位置
DirectiveTypedi;//往下个坐标位置方向
}SElemType;

typedefstruct...{
SElemType*base;
SElemType*top;
stacksize;
}SqStack;

//-----------------栈基本操作算法实现--------------------------------
StatusInitStack(SqStack&s)...{ [Page]
s.base=(SElemType*)malloc(STACK_INIT_SIZE*(SElemType));
(!s.base)exit(OVERFLOW);
s.top=s.base;
s.stacksize=STACK_INIT_SIZE;
OK;
}

StatusGetTop(SqStacks,SElemType&e)...{
(s.tops.base)ERROR;
e=*(s.top-1);
OK;
}

StatusPush(SqStack&s,SElemTypee)...{
(s.top-s.base>=s.stacksize)...{//栈满追加存储空间
s.base=(SElemType*)realloc(s.base,(s.stacksize+STACKINCREMENT)*(SElemType));
(!s.base)exit(OVERFLOW);
s.top=s.base+s.stacksize;
s.stacksizeSTACKINCREMENT;
}
*s.top+e;
OK;
}

StatusPop(SqStack&s,SElemType&e)...{
(s.tops.base)ERROR;
e=*--s.top;
OK;
}

StackEmpty(SqStacks)
...{
s.bases.top;
}

StatusClearStack(SqStack&s)
...{
s.top=s.base;
OK;
}
//~
3

//maze.h
//--------------------迷宫----------------------------------
/**//**************************************************************
迷宫问题算法:从入口出发,顺着某个方向进行探索,若能走通,则继续
前进;否则沿着原路退回,换个方向继续探索,直至出口位置,求得条通路,


假如所有可能通路都探索到而未能达到出口,则所设定迷宫没有通路.
介绍说明:可通:未增走到过通道快.
*********************************************************/
#ROW9//迷宫行数
#COL8//迷宫列数

typedefstruct...{
m,n; [Page]
arr[RANGE][RANGE];
}MazeType;//迷宫类型

StatusInitMaze(MazeType&maze,a[COL],row,col)...{
//按照用户输入row行和col列 2维(0/1)
//设置迷宫maze初值,包括加上边缘圈值
for(i=1;i<=row;i)...{
for(j=1;j<=col;j)...{
maze.arr[i][j]=a[i-1][j-1];
}
}
//加上围墙
for(j=0;j<=col+1;j)...{
maze.arr[0][j]=maze.arr[row+1][j]=1;
}
for(i=0;i<=row+1;i)...{
maze.arr[i][0]=maze.arr[i][col+1]=1;
}
maze.m=row,maze.n=col;
OK;
}

StatusPass(MazeTypemaze,PosTypecurpos)...{
//判断当前节点是否通过
maze.arr[curpos.row][curpos.col]0;
}

StatusFootPr(MazeType&maze,PosTypecurpos)...{
//留下足迹
maze.arr[curpos.row][curpos.col]=’*’;
OK;
}

StatusMarkPr(MazeType&maze,PosTypecurpos)...{
//留下不能通过标记
maze.arr[curpos.row][curpos.col]=’@’;
OK;
}

SElemTypeCreateSElem(step,PosTypepos,di)...{
SElemTypee;
e.step=step;e.seat=pos;e.di=di;
e;
}

PosTypeNextPos(PosTypecurpos,DirectiveTypedi)...{
//返回当前节点下节点
PosTypepos=curpos;
switch(di)
...{
1://东 [Page]
pos.col;
;
2://南
pos.row;
;
3://西
pos.col--;
;
4://北
pos.row--;
;
}
pos;
}

StatusPosEquare(PosTypepos1,PosTypepos2)...{
//判断两节点是否相等
pos1.rowpos2.row&&pos1.colpos2.col;
}

voidPrMaze(MazeTypemaze,row,col)...{
//打印迷宫信息
for(i=1;i<=row;i)...{
for(j=1;j<=col;j)...{
switch(maze.arr[i][j])
...{
0:
prf(\"\");
;
’*’:


prf(\"*\");
;
’@’:
prf(\"@\");
;
1:
prf(\"#\"); [Page]
;
}
}
prf(\"\");
}
}

StatusMazePath(MazeType&maze,PosTypestart,PosTypeend)...{
//求解迷宫maze中,从入口start到出口end条路径
//若存在,返回TRUE,否则返回FALSE
SqStacks;SElemTypee;
InitStack(s);
PosTypecurpos=start;
curstep=1;//探索第部
do...{
(Pass(maze,curpos))...{//如果当前位置可以通过,即是未曾走到通道块
FootPr(maze,curpos);//留下足迹
e=CreateSElem(curstep,curpos,1);//创建元素
Push(s,e);
(PosEquare(curpos,end))TRUE;
curpos=NextPos(curpos,1);//获得下节点:当前位置东邻
curstep;//探索下步
}...{//当前位置不能通过
(!StackEmpty(s))...{
Pop(s,e); [Page]
while(e.di4&&!StackEmpty(s))...{
MarkPr(maze,e.seat);Pop(s,e);curstep--;//留下不能通过标记,并退回步
}
(e.di<4)...{
e.di;Push(s,e);//换个方向探索
curpos=NextPos(e.seat,e.di);//求下个节点
}
}
}
}while(!StackEmpty(s));
FALSE;
}
//~

4

//test.cpp
#\"base.h\"
#\"stack.h\"
#\"maze.h\"



/**//****************测试***********************************/
void
...{
a[ROW][COL];
prf(\"enterthemaze’sdata:\");
for(i=0;i<ROW;i)
...{
for(j=0;j<COL;j)
...{
scanf(\"%d\",&a[i][j]);
}
}
PosTypestart,end;
start.row=1;start.col=1;
end.row=9;end.col=8;
MazeTypemaze; [Page]
InitMaze(maze,a,ROW,COL);
Statusok=MazePath(maze,start,end);
(ok)PrMaze(maze,ROW,COL);
prf(\"没有找到通路\");
}
//~

延伸阅读

• 2009-1-9-- 编译调试:C#代码动态编译、动态执行、动态调试
• 2011-6-9-- 电视棒代码,最棒的程序代码，不是程序代码
• 2008-9-10-- 代码实现窗体升起:C#代码实现ControlTemplate
• 2008-12-12-- c语言代码优化:如何优化C语言代码
• 2011-3-28-- 程序代码,我见过的最糟糕的程序代码
• 2009-1-9-- controltemplate:有关C#代码实现ControlTemplate
• 2009-2-12-- c语言程序代码:C语言程序代码的优化方法
• 2008-9-10-- 代码实现窗体升起:关于C#代码实现ControlTemplate
• 2008-12-10-- c语言代码:从汇编语言翻译到c语言代码
• 2009-8-16-- c语言代码:编写高效简洁的C语言代码