1.用栈实现迷宫问题求解
2.老鼠走迷宫程序实例
1.用栈实现迷宫问题求解
源程序：
//base.h
#include
#include
#include
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status
//stack.h
#include "base.h"
#define INIT_SIZE 100 //存储空间初始分配量
#define INCREMENT 10 //存储空间分配增量
typedef struct{ //迷宫中r行c列的位置
int r
int c
}PostType
typedef struct{
int ord //当前位置在路径上的序号
PostType seat//当前坐标
int di //往下一坐标的方向
}SElemType //栈元素类型
typedef struct{
SElemType* base//栈基址,构造前销毁后为空
SElemType* top//栈顶
int stackSize //栈容量
}Stack//栈类型
Status InitStack(Stack &S){ //构造空栈s
S.base=(SElemType*)malloc(INIT_SIZE *sizeof(SElemType))
if(!S.base)
exit(OVERFLOW)//存储分配失败
S.top=S.base
S.stackSize=INIT_SIZE
return OK
}//InitStack
Status StackEmpty(Stack S){
//若s为空返回TRUE,否则返回FALSE
if(S.top==S.base)
return TRUE
return FALSE
}//StackEmpty
Status Push(Stack &S,SElemType e){
//插入元素e为新的栈顶元素
if(S.top-S.base >=S.stackSize){//栈满，加空间
S.base=(SElemType *)realloc(S.base,(S.stackSize+INCREMENT)*sizeof(SElemType))
if(!S.base)
exit(OVERFLOW) //存储分配失败
S.top=S.base+S.stackSize
S.stackSize+=INCREMENT
}
*S.top++=e
return OK
}//push
Status Pop(Stack &S,SElemType &e){//若栈不空删除栈//顶元素用e返回并返回OK，否则返回ERROR
if(S.top==S.base)
return ERROR
e=*--S.top
return OK
}//Pop
Status DestroyStack(Stack &S){//销毁栈S,
free(S.base)
S.top=S.base
return OK
}//DestroyStack
//maze.cpp
#include "stack.h"
#define MAXLEN 10//迷宫包括外墙最大行列数目
typedef struct{
int r
int c
char adr[MAXLEN][MAXLEN]//可取’ ’’*’ ’@’ ’#’
}MazeType //迷宫类型
Status InitMaze(MazeType &maze){
//初始化迷宫若成功返回TRUE,否则返回FALSE
int m,n,i,j
printf("Enter row and column numbers: ")
scanf("%d%d",&maze.r,&maze.c)//迷宫行和列数
for(i=0i<=maze.c+1i++){//迷宫行外墙
maze.adr[0][i]=’#’
maze.adr[maze.r+1][i]=’#’
}//for
for(i=0i<=maze.r+1i++){//迷宫列外墙
maze.adr[i][0]=’#’
maze.adr[i][maze.c+1]=’#’
}
for(i=1i<=maze.ri++)
for(j=1j<=maze.cj++)
maze.adr[i][j]=’ ’//初始化迷宫
printf("Enter block’s coordinate((-1,-1) to end): ")
scanf("%d%d",&m,&n)//接收障碍的坐标
while(m!=-1){
if(m>maze.r || n>maze.c)//越界
exit(ERROR)
maze.adr[m][n]=’#’//迷宫障碍用’#’标记
printf("Enter block’s coordinate((-1,-1) to end): ")
scanf("%d%d",&m,&n)
}//while
return OK
}//InitMaze
Status Pass(MazeType maze,PostType curpos){
//当前位置可通则返回TURE,否则返回FALSE
if(maze.adr[curpos.r][curpos.c]==’ ’)//可通
return TRUE
else
return FALSE
}//Pass
Status FootPrint(MazeType &maze,PostType curpos){
//若走过并且可通返回TRUE,否则返回FALSE
//在返回之前销毁栈S
maze.adr[curpos.r][curpos.c]=’*’//"*"表示可通
return OK
}//FootPrint
PostType NextPos(PostType &curpos,int i){
//指示并返回下一位置的坐标
PostType cpos
cpos=curpos
switch(i){//1.2.3.4分别表示东,南,西,北方向
case 1 : cpos.c+=1break
case 2 : cpos.r+=1break
case 3 : cpos.c-=1break
case 4 : cpos.r-=1break
default: exit(ERROR)
}
return cpos
}//Nextpos
Status MarkPrint(MazeType &maze,PostType curpos){
//曾走过但不是通路标记并返回OK
maze.adr[curpos.r][curpos.c]=’@’//"@"表示曾走过但不通
return OK
}//MarkPrint
Status MazePath(MazeType &maze,PostType start,PostType end){
//若迷宫maze存在从入口start到end的通道则求得一条存放在栈中
//并返回TRUE,否则返回FALSE
Stack S
PostType curpos
int curstep//当前序号,1.2.3.4分别表示东,南,西,北方向
SElemType e
InitStack(S)
curpos=start//设置"当前位置"为"入口位置"
curstep=1 //探索第一步
do{
if(Pass(maze,curpos)){//当前位置可以通过,
//即是未曾走到过的通道
FootPrint(maze,curpos)//留下足迹
e.ord=curstep
e.seat=curpos
e.di=1
Push(S,e) //加入路径
if(curpos.r==end.r&&curpos.c==end.c)
if(!DestroyStack(S))//销毁失败
exit(OVERFLOW)
else
return TRUE//到达出口
else{
curpos=NextPos(curpos,1)
//下一位置是当前位置的东邻
curstep++ //探索下一步
}//else
}//if
else{//当前位置不通
if(!StackEmpty(S)){
Pop(S,e)
while(e.di==4
&&!StackEmpty(S)){
MarkPrint(maze,e.seat)
Pop(S,e)
//留下不能通过的标记,并退一步
}//while
if(e.di <4){
e.di++//换下一个方向探索
Push(S,e)
curpos=NextPos(e.seat,e.di)//设定当前位置是该
//新方向上的相邻
}//if
}//if
}//else
}while(!StackEmpty(S))
if(!DestroyStack(S))//销毁失败
exit(OVERFLOW)
else
return FALSE
}//MazePath
void PrintMaze(MazeType &maze){
//将标记路径信息的迷宫输出到终端(包括外墙)
int i,j
printf("\nShow maze path(*---pathway):\n\n")
printf(" ")
for(i=0i<=maze.r+1i++)//打印列数名
printf("%4d",i)
printf("\n\n")
for(i=0i<=maze.r+1i++){
printf("%2d",i)//打印行名
for(j=0j<=maze.c+1j++)
printf("%4c",maze.adr[i][j])//输出迷宫//当前位置的标记
printf("\n\n")
}
}//PrintMaze
void main(){ //主函数
MazeType maze
PostType start,end
char cmd
do{
printf("-------FOUND A MAZEPATH--------\n")
if(!InitMaze(maze)){ //初始化并创建迷宫
printf("\nInitialization errors!!!\n")
exit(OVERFLOW)//初始化错误
}
do{ //输入迷宫入口坐标
printf("\nEnter entrance coordinate of the maze: ")
scanf("%d%d",&start.r,&start.c)
if(start.r>maze.r || start.c>maze.c){
printf("\nBeyond the maze!!!\n")
continue
}
}while(start.r>maze.r || start.c>maze.c)
do{ //输入迷宫出口坐标
printf("\nEnter exit coordinate of the maze: ")
scanf("%d%d",&end.r,&end.c)
if(end.r>maze.r || end.c>maze.c){
printf("\nBeyond the maze!!!\n")
continue
}
}while(end.r>maze.r || end.c>maze.c)
if(!MazePath(maze,start,end))//迷宫求解
printf("\nNo path from entrance to exit!\n")
else
PrintMaze(maze)//打印路径
printf("\nContinue?(y/n): ")
scanf("%s",&cmd)
}while(cmd==’y’ || cmd==’Y’)
}//main
2.老鼠走迷宫程序实例
#include "stdafx.h"
#include "iostream.h"
#include "string.h"
#include "stdio.h"
double dMeans=0,dWalkLen=10000//dMeans表示走出迷宫的方法，dWalkLen表示当前走出迷宫最少步数
char Maze[10][52]={
{"###################################################"},
{"% ## #### ### ### # ####"},
{"# ## # ### ### ###### ### ############ # ##"},
{"# ## ## ### ## ## # # ## # # ####"},
{"# ## ## ## ### # # ######### # # # ##"},
{"# # # # ## ########## #### ## ##"},
{"# ## ### ## ## ### #### ##### # ######### #"},
{"# # # ## ## # ## #### # # ######"},
{"#### ## ########## # ### ####@"},
{"###################################################"},
} //迷宫
int MazeFlag[10][51] //迷宫的标志：0表示未走过，i(i=1,2,3,4)表示已经走过了,i表示方向。
int MazeMin[10][51] //路径最小的迷宫的标志
void Walk(int nx,int ny)//走迷宫的函数，nx是列，ny是行
void PrintOut()//打印路径及迷宫的函数，同时比较获取路径较短的行走方法
int Judge(int nx,int ny,int i)//判断在第nx列ny行向第i个方向走是否可以,可以返回1否则返回0。
//i=1表示向右，2表示向下，3表示向左，4表示向上
/*---------------------------------------------------------------------------------------------
//行走迷宫函数： void Walk (int nx,int ny)
//功能：判断是否已经走出迷宫，如果走出则打印路径，如果没有则开始逐个方向判断是否可以行走，
// 如果都不能行走，或已经返回。则退出该位置，即将该位置的标志写为0表明未走过。
//无返回值，形参nx为当前位置的列，ny为当前位置的行。
---------------------------------------------------------------------------------------------*/
void Walk(int nx,int ny)
{
if (Maze[nx][ny]=='@')//判断是否走出迷宫，@是迷宫出口标志
PrintOut() //走出则打印出迷宫及行走路径
else //未走出迷宫
{
for (int i=1i<=4i++)//四个方向逐个行走，i=1向右 2向下 3向左 4向上
{
if (Judge(nx,ny,i)) //如果列为nx行为ny的位置向i方向是否可以行走
{
MazeFlag[nx][ny]=i//将标志位置i表明该位置向i方向可行走
if (i==1) //分散处理，根据不同的i来确定下一步的位置，以便行走。
Walk(nx,ny+1)
else if (i==2)
Walk(nx+1,ny)
else if (i==3)
Walk(nx,ny-1)
else if (i==4)
Walk(nx-1,ny)
}
}
MazeFlag[nx][ny]=0//如果4个方向都走不通，或者回朔则清空该点标志位，置为0表明未走过。
}
}
/*---------------------------------------------------------------------------------------------
//打印函数：void PrintOut()
//功能：打印第dMeans种方法的在迷宫中的行走路径,以及通过比较找出目前行走步数最少的行走方法。
//无返回值，无形参。dMeans表示当前行走方法的种类。dCount是用来计算此种方法用了多少步。
---------------------------------------------------------------------------------------------*/
void PrintOut()
{
int nx,ny
double dCount=0
dMeans++
cout<<"The "<<dMeans<<" ways is: "<<endl
for (nx=0nx<10nx++)
{
for (ny=0ny<51ny++)
{
if (Maze[nx][ny]=='#')//＃表示墙
cout<<"#"
else if (MazeFlag[nx][ny]==0)//不是墙但未走过的地方用空格表示
cout<<" "
else //不是墙且走过的地方用*表示
{
cout<<"."
dCount++ //走一步总步数加1
}
}
cout<<endl
}
cout<<"This way used "<<dCount<<" steps"<<endl
if (dCount<dWalkLen)//如果此种方法的步数比以前方法中最少步数还要少，
{ //则将此种方法列为当前最少行走步数
for (nx=0nx<10nx++)
for(ny=0ny<51ny++)
MazeMin[nx][ny]=MazeFlag[nx][ny]
dWalkLen=dCount
}
}
/*--------------------------------------------------------------------------------------------
//判断函数：int Judge(int nx,int ny,int i)
//功能：判断当前位置(nx为列ny为行)向第i方向行走是否可以
//返回值int型 返回1表明可以，0表示不可以
--------------------------------------------------------------------------------------------*/
int Judge(int nx,int ny,int i)
{
if (i==1)//判断向右可否行走
{
if (ny<50&&(Maze[nx][ny+1]==' '||Maze[nx][ny+1]=='@')&&MazeFlag[nx][ny+1]==0)
return 1
else
return 0
}
else if (i==2)//判断向下可否行走
{
if (nx<9&&(Maze[nx+1][ny]==' '||Maze[nx+1][ny]=='@')&&MazeFlag[nx+1][ny]==0)
return 1
else
return 0
}
else if (i==3)//判断向左可否行走
{
if (ny>0&&(Maze[nx][ny-1]==' '||Maze[nx][ny-1]=='@')&&MazeFlag[nx][ny-1]==0)
return 1
else
return 0
}
else if (i==4)//判断向上可否行走
{
if (nx>0&&(Maze[nx-1][ny]==' '||Maze[nx-1][ny]=='@')&&MazeFlag[nx-1][ny]==0)
return 1
else
return 0
}
else
return 0
}
int main(int argc, char* argv[])
{
int nx,ny,ni,nj
cout<<"迷宫游戏: "<<endl
for (ni=0ni<10ni++)//输出迷宫形状，并且找到迷宫的入口，同时将迷宫标志初始化
{
for(nj=0nj<51nj++)
{
cout<<Maze[ni][nj]
MazeFlag[ni][nj]=0//将迷宫标志初始化为0表示未走过
if (Maze[ni][nj]=='%')
{
nx=ni//迷宫入口列坐标
ny=nj//迷宫入口行坐标
}
}
cout<<endl
}
cout<<endl<<"入口坐标:"<<endl<<"nx= "<<nx<<" "<<"ny= "<<ny<<endl
Walk(nx,ny)//调用行走迷宫函数，从入口处开始行走
cout<<endl<<"The MinLen way is: "<<endl
for (nx=0nx<10nx++)//输出最短路径
{
for (ny=0ny<51ny++)
{
if (Maze[nx][ny]=='#')
cout<<"#"
else if (MazeMin[nx][ny]==0)
cout<<" "
else
{
cout<<"."
}
}
cout<<endl
}
cout<<"This Way used "<<dWalkLen<<" steps"<<endl//输出最短路径总行走步数
return 0
}
#include <graphics.h>#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
#include <dos.h>
#define N 20/*
迷宫的大小，可改变
*/
int oldmap[N][N]/*
递归用的数组
,
用全局变量节约时间
*/
int yes=0/*yes
是判断是否找到路的标志
,1
找到，
0
没找到
*/
int way[100][2],wayn=0/*way
数组是显示路线用的
,wayn
是统计走了几个格
子
*/
void Init(void)/*
图形初始化
*/
void Close(void)/*
图形关闭
*/
void DrawPeople(int *x,int *y,int n)/*
画人工探索物图
*/
void PeopleFind(int (*x)[N])/*
人工探索
*/
void
WayCopy(int
(*x)[N],int
(*y)[N])/*
为了
8
个方向的递归，把旧迷宫图
拷贝给新数组
*/
int FindWay(int (*x)[N],int i,int j)/*
自动探索函数
*/
void MapRand(int (*x)[N])/*
随机生成迷宫函数
*/
void PrMap(int (*x)[N])/*
输出迷宫图函数
*/
void Result(void)/*
输出结果处理
*/
void Find(void)/*
成功处理
*/
void NotFind(void)/*
失败处理
*/
void main(void)/*
主函数
*/
{
int map[N][N]/*
迷宫数组
*/
char ch
clrscr()
printf("\n Please select hand(1) else auto\n")/*
选择探索方式
*/
scanf("%c",&ch)
Init() /*
初始化
*/
MapRand(map)/*
生成迷宫
*/
PrMap(map)/*
显示迷宫图
*/
if(ch=='1')
PeopleFind(map)/*
人工探索
*/
else
FindWay(map,1,1)/*
系统自动从下标
1,1
的地方开始探索
*/
Result()/*
输出结果
*/
Close()
}
void Init(void)/*
图形初始化
*/
{
int gd=DETECT,gm
initgraph(&gd,&gm,"c:\\tc")}
void DrawPeople(int *x,int *y,int n)/*画人工控制图*/ {/*如果将以下两句注释掉，则显示人工走过的路径，*/
setfillstyle(SOLID_FILL,WHITE) /*设置白色实体填充样式*/bar(100+(*y)*15-6,50+(*x)*15-6,100+(*y)*15+6,50+(*x)*15+6)/*恢复原通路*/
switch(n)/*判断x,y的变化，8个方向的变化*/{
case 1: (*x)--break/*上*/
case 2: (*x)--(*y)++break /*右上*/ case 3: (*y)++break /*右*/
case 4: (*x)++(*y)++break/*右下*/ case 5: (*x)++break /*下*/
case 6: (*x)++(*y)--break/*左下*/ case 7: (*y)--break /*左*/
case 8: (*x)--(*y)--break/*左上*/}
setfillstyle(SOLID_FILL,RED)/*新位置显示探索物*/
bar(100+(*y)*15-6,50+(*x)*15-6,100+(*y)*15+6,50+(*x)*15+6)}
void PeopleFind(int (*map)[N])/*人工手动查找*/ {
int x,y
char c=0/*接收按键的变量*/x=y=1/*人工查找的初始位置*/setcolor(11)
line(500,200,550,200) outtextxy(570,197,"d") line(500,200,450,200) outtextxy(430,197,"a") line(500,200,500,150) outtextxy(497,130,"w") line(500,200,500,250) outtextxy(497,270,"x") line(500,200,450,150) outtextxy(445,130,"q") line(500,200,550,150) outtextxy(550,130,"e") line(500,200,450,250) outtextxy(445,270,"z") line(500,200,550,250)
outtextxy(550,270,"c")/*以上是画8个方向的控制介绍*/
setcolor(YELLOW)
outtextxy(420,290,"Press 'Enter' to end")/*压回车键结束*/setfillstyle(SOLID_FILL,RED)
bar(100+y*15-6,50+x*15-6,100+y*15+6,50+x*15+6)/*入口位置显示*/while(c!=13)/*如果按下的不是回车键*/{
c=getch()/*接收字符后开始各个方向的探索*/ if(c=='w'&&map[x-1][y]!=1) DrawPeople(&x,&y,1)/*上*/ else if(c=='e'&&map[x-1][y+1]!=1) DrawPeople(&x,&y,2)/*右上*/ else if(c=='d'&&map[x][y+1]!=1) DrawPeople(&x,&y,3)/*右*/ else if(c=='c'&&map[x+1][y+1]!=1) DrawPeople(&x,&y,4)/*右下*/ else if(c=='x'&&map[x+1][y]!=1)DrawPeople(&x,&y,5)/*下*/ elseif(c=='z'&&map[x+1][y-1]!=1)DrawPeople(&x,&y,6)/*左下*/elseif(c=='a'&&map[x][y-1]!=1) DrawPeople(&x,&y,7)/*左*/else if(c=='q'&&map[x-1][y-1]!=1) DrawPeople(&x,&y,8)/*左上*/}
setfillstyle(SOLID_FILL,WHITE)/*消去红色探索物，恢复原迷宫图*/bar(100+y*15-6,50+x*15-6,100+y*15+6,50+x*15+6) if(x==N-2&&y==N-2)/*人工控制找成功的话*/ yes=1/*如果成功标志为1*/ }
void WayCopy(int (*oldmap)[N],int (*map)[N])/*拷贝迷宫数组 */ {
int i,j
for(i=0i<Ni++) for(j=0j<Nj++) oldmap[i][j]=map[i][j]}
int FindWay(int (*map)[N],int i,int j)/*递归找路*/ {
if(i==N-2&&j==N-2)/*走到出口*/{
yes=1/*标志为1,表示成功*/ return }
map[i][j]=1/*走过的地方变为1*/WayCopy(oldmap,map)/*拷贝迷宫图*/
if(oldmap[i+1][j+1]==0&&!yes)/*判断右下方是否可走*/{
FindWay(oldmap,i+1,j+1) if(yes)/*如果到达出口了，再把值赋给显示路线的way数组,也正是这个原因,所以具体路线是从最后开始保存*/ { way[wayn][0]=i way[wayn++][1]=j return }}
WayCopy(oldmap,map)
if(oldmap[i+1][j]==0&&!yes)/*判断下方是否可以走,如果标志yes已经是1也不用找下去了*/{
FindWay(oldmap,i+1,j) if(yes) { way[wayn][0]=i way[wayn++][1]=j return }}
WayCopy(oldmap,map)
if(oldmap[i][j+1]==0&&!yes)/*判断右方是否可以走*/{
FindWay(oldmap,i,j+1) if(yes) { way[wayn][0]=i way[wayn++][1]=j return }}
WayCopy(oldmap,map)
if(oldmap[i-1][j]==0&&!yes)/*判断上方是否可以走*/{
FindWay(oldmap,i-1,j) if(yes) { way[wayn][0]=i way[wayn++][1]=j return }}
WayCopy(oldmap,map)
if(oldmap[i-1][j+1]==0&&!yes)/*判断右上方是否可以走*/{
FindWay(oldmap,i-1,j+1) if(yes) { way[wayn][0]=i way[wayn++][1]=j return }}
WayCopy(oldmap,map)
if(oldmap[i+1][j-1]==0&&!yes)/*判断左下方是否可以走*/{
FindWay(oldmap,i+1,j-1) if(yes) { way[wayn][0]=i way[wayn++][1]=j return }}
WayCopy(oldmap,map)
if(oldmap[i][j-1]==0&&!yes)/*判断左方是否可以走*/{
FindWay(oldmap,i,j-1) if(yes) { way[wayn][0]=i way[wayn++][1]=j return }}
WayCopy(oldmap,map)
if(oldmap[i-1][j-1]==0&&!yes)/*判断左上方是否可以走*/{
FindWay(oldmap,i-1,j-1) if(yes) { way[wayn][0]=i way[wayn++][1]=j return }}
return}
void MapRand(int (*map)[N])/*开始的随机迷宫图*/ {
int i,j
cleardevice()/*清屏*/
randomize()/*随机数发生器*/for(i=0i<Ni++){
for(j=0j<Nj++) { if(i==0||i==N-1||j==0||j==N-1)/*最外面一圈为墙壁*/ map[i][j]=1 else if(i==1&&j==1||i==N-2&&j==N-2)/*出发点与终点表示为可走的*/ map[i][j]=0 else map[i][j]=random(2)/*其它的随机生成0或1*/ }} }
void PrMap(int (*map)[N])/*输出迷宫图*/ {
int i,j
for(i=0i<Ni++) for(j=0j<Nj++) if(map[i][j]==0) { setfillstyle(SOLID_FILL,WHITE)/*白色为可走的路*/ bar(100+j*15-6,50+i*15-6,100+j*15+6,50+i*15+6) } else { setfillstyle(SOLID_FILL,BLUE)/*蓝色为墙壁*/ bar(100+j*15-6,50+i*15-6,100+j*15+6,50+i*15+6)
} }
void Find(void)/*找到通路*/ {
int i
setfillstyle(SOLID_FILL,RED)/*红色输出走的具体路线*/wayn--
for(i=wayni>=0i--){
bar(100+way[i][1]*15-6,50+way[i][0]*15-6,100+ way[i][1]*15+6,50+way[i][0]*15+6) sleep(1)/*控制显示时间*/}
bar(100+(N-2)*15-6,50+(N-2)*15-6,100+ (N-2)*15+6,50+(N-2)*15+6)/*在目标点标红色*/setcolor(GREEN)
settextstyle(0,0,2)/*设置字体大小*/outtextxy(130,400,"Find a way!")}
void NotFind(void)/*没找到通路*/ {
setcolor(GREEN)
settextstyle(0,0,2)/*设置字体大小*/outtextxy(130,400,"Not find a way!")}
void Result(void)/*结果处理*/ {
if(yes)/*如果找到*/ Find()
else/*没找到路*/ NotFind() getch()}
void Close(void)/*图形关闭*/ {
closegraph()}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）