#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()}
程序目的：输入一个任意大小的迷宫，用栈求出一条走出迷宫的路径，并
显示在屏幕上。
程序实现：
可以实现载入迷宫和保存迷宫，附带文件中有4个测试迷宫路径的
文件test1~4.dd。请将这些文件拷贝到TC当前目录下，或者在载
入时写明完全路径。由于屏幕大小的限制，当用户自己输入迷宫
时一定要注意：迷宫大小是有限制的，不小于4*3,不大于30*20。
否则会出现错误信息。输入开始时全是墙，用上下左右键移动，
用Del键删除墙，形成通路，用Enter键添加墙。输入结束时可以
将迷宫保存下来，以dd为扩展名。输入完毕时用F9键来得到结果，
找到路径时，屏幕下方会出现Path found，否则出现Path not found。
程序经Turbo C 2.0编译调试成功。运行时不用添加任何运行库。
不可以在VC上编译。
下载DOS版和windows版的迷宫游戏全部代码
用户名：migong
----------------------------------------------------------------------------------
/**//*
MazePath Demo BY Turbo C 2.0
Copyright(c) RoverUnion. All right reserved.
Filename: Maze.c
Author Dongchengyu.
Ver 1.10
*/
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <conio.h>
#include <dos.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define F9 0x43
#define Esc 0x1b
#define Del 0x53
#define Home 0x47
#define End 0x4f
#define Space 0x20
#define Up 0x48
#define Down 0x50
#define Left 0x4b
#define Right 0x4d
#define Enter 0x0d
#define F2 0x3c
#define F3 0x3d
#define STACK_INIT_SIZE 200
#define STACKINCREMENT 10
typedef int Boolean
typedef int Status
typedef struct {
int x
int y
} PosType
typedef struct {
int ord
PosType seat
int di
} SElemType
typedef struct {
int td
int foot
int mark
} MazeType
typedef struct {
SElemType *base
SElemType *top
int stacksize
} Stack
int Maze[20][30]
MazeType maze[20][30]
PosType StartPlace
PosType EndPlace
int count
int m,n
Boolean b_start=FALSE,b_end=FALSE
void CreatMaze(void)
Status SaveMaze(char *filename)
Status LoadMaze(char *filename)
void Error(char *message)
Status InitStack(Stack *s)
Status DestroyStack(Stack *s)
Status ClearStack(Stack *s)
Boolean StackEmpty(Stack *s)
int StackLength(Stack *s)
Status Push(Stack *s,SElemType e)
SElemType Pop(Stack *s,SElemType e)
Status GetTop(Stack *s,SElemType *e)
Status StackTraverse(Stack *s,Status (* visit)(SElemType *se))
Boolean Pass(PosType curpos)
void MarkPrint(PosType seat)
void FootPrint(PosType curpos)
PosType NextPos(PosType seat,int di)
Status MazePath(PosType start,PosType end)
void CreatMaze(void)
/**//* Form the maze. */
{
void Error(char *message)
Status SaveMaze(char *filename)
Status LoadMaze(char *filename)
int i,j
int x,y
char c
char savename[12],loadname[12]
Boolean flag=FALSE,load=FALSE
clrscr()
printf("Menu:\n\n")
printf("1.Load Mazefile:(*.dd)\n\n")
printf("2.Input Maze:\n\n")
printf("Input your choice: ")
do
{
c=getch()
switch(c)
{
case ''''''''''''''''''''''''''''''''1'''''''''''''''''''''''''''''''': putch(''''''''''''''''''''''''''''''''1'''''''''''''''''''''''''''''''')break
case ''''''''''''''''''''''''''''''''2'''''''''''''''''''''''''''''''': putch(''''''''''''''''''''''''''''''''2'''''''''''''''''''''''''''''''')break
case Esc: sleep(1)exit(1)
default: break
}
}
while(c!=''''''''''''''''''''''''''''''''1''''''''''''''''''''''''''''''''&&c!=''''''''''''''''''''''''''''''''2'''''''''''''''''''''''''''''''')
if(c==''''''''''''''''''''''''''''''''1'''''''''''''''''''''''''''''''')
{
printf("\n\nLoadName: ")
scanf("%s",loadname)
if(LoadMaze(loadname))
{
sleep(1)load=TRUE
}
else { gotoxy(1,9)printf("Load fail! ")}
}
if(!load)
{
printf("\nInput the maze''''''''''''''''''''''''''''''''s size:\n")
printf("\nInput Length :\n")
scanf("%d",&m)
printf("\nInput Width :\n")
scanf("%d",&n)
if(m<4||n<4) Error("Input")
if(m>30||n>20) Error("Maze too large")
for(i=0i<30i++)
for(j=0j<20j++)
Maze[j][i]=2
StartPlace.x=0
StartPlace.y=0
EndPlace.x=0
EndPlace.y=0
clrscr()
printf("\n")
for(i=1i<=ni++)
{
for(j=1j<=mj++)
{
printf(" #")
Maze[i-1][j-1]=0
}
printf("\n")
}
}
gotoxy(65,5)
printf("''''''''''''''''''''''''''''''''#'''''''''''''''''''''''''''''''':Wall")
gotoxy(65,7)
printf("Start:Home")
gotoxy(65,9)
printf("End:End")
gotoxy(65,11)
printf("Delete Wall:Del")
gotoxy(65,13)
printf("Enter Wall:Enter")
gotoxy(65,15)
printf("Save Maze:F2")
gotoxy(65,17)
printf("Complete:F9")
gotoxy(65,19)
printf("Exit:Esc")
gotoxy(4,3)
x=4y=3
do
{
c=getch()
switch(c)
{
case Up: if(y>3) { y--gotoxy(x,y)}
break
case Down: if(y<n) { y++gotoxy(x,y)}
break
case Left: if(x>4) { x-=2gotoxy(x,y)}
break
case Right: if(x<2*m-2) { x+=2gotoxy(x,y)}
break
case Del: if(y-2==StartPlace.y&&x/2-1==StartPlace.x) b_start=FALSE
if(y-2==EndPlace.y&&x/2-1==EndPlace.x) b_end=FALSE
putch('''''''''''''''''''''''''''''''' '''''''''''''''''''''''''''''''')Maze[y-2][x/2-1]=1gotoxy(x,y)
break
case Enter: if(y-2==StartPlace.y&&x/2-1==StartPlace.x) break
if(y-2==EndPlace.y&&x/2-1==EndPlace.x) break
putch(''''''''''''''''''''''''''''''''#'''''''''''''''''''''''''''''''')Maze[y-2][x/2-1]=0gotoxy(x,y)
break
case Home: if(Maze[y-2][x/2-1]&&!b_start)
{
StartPlace.x=x/2-1
StartPlace.y=y-2
putch(''''''''''''''''''''''''''''''''S'''''''''''''''''''''''''''''''')
gotoxy(x,y)
b_start=TRUE
}
break
case End: if(Maze[y-2][x/2-1]&&!b_end)
{
EndPlace.x=x/2-1
EndPlace.y=y-2
putch(''''''''''''''''''''''''''''''''E'''''''''''''''''''''''''''''''')
gotoxy(x,y)
b_end=TRUE
}
break
case Esc: gotoxy(2,22)printf("exit")sleep(1)exit(1)
case F9: if(b_start&&b_end) flag=TRUEbreak
case F2: gotoxy(2,22)
printf("Savename:")
scanf("%s",savename)
gotoxy(2,22)
if(SaveMaze(savename)) printf("Save OK! ")
else printf("Save fail! ")
sleep(1)
gotoxy(2,22)
printf(" ")
gotoxy(x,y)
break
default: break
}
}
while(!flag)
for(i=0i<30i++)
for(j=0j<20j++)
{
maze[j][i].td=Maze[j][i]
maze[j][i].mark=0
maze[j][i].foot=0
}
}
Status LoadMaze(char *file)
/**//* The maze has been loaded. */
{
FILE *fp
char *buffer
char ch
int i=0,j,k
Boolean len=FALSE,wid=FALSE
if((fp=fopen(file,"r"))==NULL)
return ERROR
buffer=(char *)malloc(600*sizeof(char))
ch=fgetc(fp)
while(ch!=EOF)
{
buffer[i]=ch
i++
ch=fgetc(fp)
}
m=30n=20
for(i=0i<600i++)
{
j=i/30k=i%30
if(buffer[i]==''''''''''''''''''''''''''''''''2''''''''''''''''''''''''''''''''&&!len){ m=ilen=TRUE}
if(k==0&&buffer[i]==''''''''''''''''''''''''''''''''2''''''''''''''''''''''''''''''''&&!wid){ n=jwid=TRUE}
switch(buffer[i])
{
case ''''''''''''''''''''''''''''''''0'''''''''''''''''''''''''''''''': Maze[j][k]=0break
case ''''''''''''''''''''''''''''''''1'''''''''''''''''''''''''''''''': Maze[j][k]=1break
case ''''''''''''''''''''''''''''''''2'''''''''''''''''''''''''''''''': Maze[j][k]=2break
case ''''''''''''''''''''''''''''''''3'''''''''''''''''''''''''''''''': Maze[j][k]=1
StartPlace.x=k
StartPlace.y=j
b_start=TRUE
break
case ''''''''''''''''''''''''''''''''4'''''''''''''''''''''''''''''''': Maze[j][k]=1
EndPlace.x=k
EndPlace.y=j
b_end=TRUE
break
default : break
}
}
fclose(fp)
clrscr()
for(i=0i<30i++)
for(j=0j<20j++)
{
maze[j][i].td=Maze[j][i]
maze[j][i].foot=0
maze[j][i].mark=0
if(Maze[j][i]==0)
{
gotoxy(2*i+2,j+2)
putch(''''''''''''''''''''''''''''''''#'''''''''''''''''''''''''''''''')
}
}
gotoxy(2*StartPlace.x+2,StartPlace.y+2)
putch(''''''''''''''''''''''''''''''''S'''''''''''''''''''''''''''''''')
gotoxy(2*EndPlace.x+2,EndPlace.y+2)
putch(''''''''''''''''''''''''''''''''E'''''''''''''''''''''''''''''''')
return OK
}
Status SaveMaze(char *filename)
/**//* The maze has been saved. */
{
FILE *fp
char *buffer
int i,j,k
fp=fopen(filename,"wb")
buffer=(char *)malloc(600*sizeof(char))
for(i=0i<600i++)
{
j=i/30k=i%30
switch(Maze[j][k])
{
case 0: buffer[i]=''''''''''''''''''''''''''''''''0''''''''''''''''''''''''''''''''break
case 1: buffer[i]=''''''''''''''''''''''''''''''''1''''''''''''''''''''''''''''''''break
case 2: buffer[i]=''''''''''''''''''''''''''''''''2''''''''''''''''''''''''''''''''break
default : Error("Write")break
}
if(k==StartPlace.x&&j==StartPlace.y) buffer[i]=''''''''''''''''''''''''''''''''3''''''''''''''''''''''''''''''''
if(k==EndPlace.x&&j==EndPlace.y) buffer[i]=''''''''''''''''''''''''''''''''4''''''''''''''''''''''''''''''''
}
fwrite(buffer,600,1,fp)
free(buffer)
fclose(fp)
return OK
}
void Error(char *message)
{
clrscr()
fprintf(stderr,"Error:%s\n",message)
exit(1)
} /**//* Error */
Status InitStack(Stack *s)
/**//* The stack s has been created and is initialized to be empty. */
{
s->base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType))
if(!s->base) Error("Overflow")
s->top=s->base
s->stacksize=STACK_INIT_SIZE
return OK
} /**//* InitStack */
Status DestroyStack(Stack *s)
/**//* The stack s has been destroyed. */
{
s->top=NULL
s->stacksize=0
free(s->base)
s->base=NULL
return OK
} /**//* DestroyStack */
Status ClearStack(Stack *s)
/**//* The stack has been clear to be maximum. */
{
s->top=s->base
s->stacksize=STACK_INIT_SIZE
return OK
} /**//* ClearStack */
Boolean StackEmpty(Stack *s)
/**//* Check if the stack s is empty. */
{
if(s->top==s->base) return TRUE
else return FALSE
} /**//* StackEmpty */
int StackLength(Stack *s)
/**//* Gain the length of the stack s. */
{
if(s->top>s->base) return (int)(s->top-s->base)
else return 0
} /**//* StackLength */
Status Push(Stack *s,SElemType e)
/**//* The element e has been pushed into the stack s. */
{
if(s->top-s->base>=s->stacksize)
{
s->base=(SElemType *)realloc(s->base,
(s->stacksize+STACKINCREMENT)*sizeof(SElemType))
if(!s->base) Error("Overflow")
s->top=s->base+s->stacksize
s->stacksize+=STACKINCREMENT
}
*s->top++=e
return OK
} /**//* Push */
SElemType Pop(Stack *s,SElemType e)
/**//* The element e has been removed from the stack s. */
{
if(s->top==s->base) Error("Pop")
e=*--s->top
return e
} /**//* Pop */
Status GetTop(Stack *s,SElemType *e)
/**//* The element e has got to the top of the stack s.*/
{
if(s->top==s->base) Error("GetTop")
*e=*(s->top-1)
return OK
} /**//* GetTop */
/**//* Traverse the stack s using ''''''''''''''''''''''''''''''''visiting'''''''''''''''''''''''''''''''' function. */
/**//* Status StackTraverse(Stack *s,Status (* visit)(SElemType *se))
{
SElemType p
int result
if(s->top==s->base) return ERROR
p=s->base
while(!(p==s->top))
{
result=(*visit)(p)
p++
}
return OK
} */
Boolean Pass(PosType curpos)
/**//* Check if the current position can be passed. */
{
if(maze[curpos.x][curpos.y].td==1&&
maze[curpos.x][curpos.y].foot==0&&maze[curpos.x][curpos.y].mark==0)
return TRUE
else return FALSE
} /**//* Pass */
void MarkPrint(PosType seat)
/**//* Mark the position seat. */
{
maze[seat.x][seat.y].mark=-1
/**//* Marking ''''''''''''''''''''''''''''''''-1'''''''''''''''''''''''''''''''' symbolize the current position cannot be put. */
} /**//* MarkPrint */
void FootPrint(PosType curpos)
/**//* The foot of the curpos of the maze has been set ''''''''''''''''''''''''''''''''true''''''''''''''''''''''''''''''''. */
{
maze[curpos.x][curpos.y].foot=1
} /**//* FootPrint */
PosType NextPos(PosType seat,int di)
{
switch(di)
{
case 1: seat.y++return seat/**//* Eastward */
case 2: seat.x++return seat/**//* Southward */
case 3: seat.y--return seat/**//* Westward */
case 4: seat.x--return seat/**//* Northward */
default: seat.x=0seat.y=0return seat
}
} /**//* NextPos */
/**//* The key to the program. */
/**//* Pre: The maze array &the startplace &the endplace.
Post: Find the one traverse of the maze and perform the mazepath.
Uses: The ADT stack class.
*/
Status MazePath(PosType start,PosType end)
{
PosType curpos
int curstep
SElemType e
Stack *s,stack
stack.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType))
if(!stack.base) Error("Overflow")
stack.top=stack.base
stack.stacksize=STACK_INIT_SIZE
s=&stack
curpos=start
curstep=1
do
{
if(Pass(curpos))
{
FootPrint(curpos)
e.ord=curstepe.seat=curpose.di=1
gotoxy((curpos.y+1)*2,curpos.x+2)
putch(''''''''''''''''''''''''''''''''@'''''''''''''''''''''''''''''''')
delay(8000)/**//* pospone time. */
Push(s,e)
if(curpos.x==end.x&&curpos.y==end.y) /**//* Proceed recursively. */
{
DestroyStack(s)
return TRUE
}
curpos=NextPos(curpos,1)/**//* Try next position. */
curstep++
}
else
{
if(!StackEmpty(s))
{
e=Pop(s,e)/**//* Removed e from s. */
while(e.di==4&&!StackEmpty(s)) /**//* Four directions have been checked
and s is not empty. */
{
MarkPrint(e.seat)
gotoxy((e.seat.y+1)*2,e.seat.x+2)
putch(''''''''''''''''''''''''''''''''@'''''''''''''''''''''''''''''''')
delay(8000)/**//* Pospone time. */
gotoxy((e.seat.y+1)*2,e.seat.x+2)
putch('''''''''''''''''''''''''''''''' '''''''''''''''''''''''''''''''')
e=Pop(s,e)/**//* Remove e from s. */
curstep--
}
if(e.di<4) /**//* The current position hasnot been checked. */
{
e.di++
Push(s,e)/**//* Insert e into s. */
curpos=NextPos(e.seat,e.di)/**//* Try next position. */
}
}
}
}
while(!StackEmpty(s))
DestroyStack(s)
return FALSE
} /**//* MazePath */
void main()
{
PosType start,end
CreatMaze()
start.x=StartPlace.y
start.y=StartPlace.x
end.x=EndPlace.y
end.y=EndPlace.x
if(MazePath(start,end))
{
gotoxy(2,22)
printf("Path found\n")
}
else
{
gotoxy(2,22)
printf("Path not found\n")
}
getch()
clrscr()
}
#include<stdio.h>#include<stdlib.h>
#define M 8
#define N 8
#define Max 100
int mg[M+2][N+2]= //定义迷宫，0表示能走的块，1表示不能走，在外围加上一圈不能走的块
{
{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}
}
struct
{
int i,j //块的位置
int pre //本路径中上一块在队列中的下标
}Qu[Max]
int front=-1,rear=-1
void print(int n)
int mgpath(int xi,int yi,int xe,int ye) //搜索算法
{
int i,j,find=0,di
rear++
Qu[rear].i=xi
Qu[rear].j=yi
Qu[rear].pre=-1
mg[1][1]=-1
while(front<=rear&&!find)
{
front++
i=Qu[front].i
j=Qu[front].j
if(i==xe&&j==ye)
{
find=1
print(front)
return(1)
}
for(di=0di<4di++)
{
switch(di) //四个方向
{
case 0:i=Qu[front].i-1j=Qu[front].jbreak
case 1:i=Qu[front].ij=Qu[front].j+1break
case 2:i=Qu[front].i+1j=Qu[front].jbreak
case 3:i=Qu[front].ij=Qu[front].j-1break
}
if(mg[i][j]==0)
{
rear++
Qu[rear].i=i
Qu[rear].j=j
Qu[rear].pre=front
mg[i][j]=-1 //避免死循环
}
}
}
return 0
}
void print(int n) //输出 路径算法
{
int k=n,j,m=1
printf("\n")
do //将输出的路径上的所有pre改为-1
{
j=k
k=Qu[k].pre
Qu[j].pre=-1
}while(k!=0)
printf("迷宫最短路径如下：\n")
k=0
while(k<Max)
{
if(Qu[k].pre==-1)
{
printf("\t(%d,%d)",Qu[k].i,Qu[k].j)
if(m%5==0)
printf("\n")
m++
}
k++
}
printf("\n")
}
int main()
{
mgpath(1,1,M,N)
system("pause")
return 0
}
