#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define stack_init_size 200
#define stack_increment 10
#define OVERFLOW 0
#define OK 1
#define ERROE 0
#define TRUE 1
#define FALSE 0
typedef int Status
typedef struct{
int x
int y
}PosType
typedef struct {
int ord// 通道块在路径上的"序号"
PosType seat//通道块在迷宫中的"坐标位置"
int di //从此通道块走向下一通道块的"方向"
}SElemType
typedef struct{
SElemType *base
SElemType *top
int stacksize
}SqStack
int mg[20][20]
/*随机生成迷宫的函数
/*为了能够让尽量能通过，将能通过的块和不能通过的块数量比大致为2:1*/
void Random(){
int i,j,k
srand(time(NULL))
mg[1][0]=mg[1][1]=mg[18][19]=0//将入口、出口设置为"0"即可通过
for(j=0j<20j++)
mg[0][j]=mg[19][j]=1 /*设置迷宫外围"不可走"，保证只有一个出口和入口*/
for(i=2i<19i++)
mg[i][0]=mg[i-1][19]=1 /*设置迷宫外围"不可走"，保证只有一个出口和入口*/
for(i=1i<19i++)
for(j=1j<19j++){
k=rand()%3//随机生成0、1、2三个数
if(k)
mg[i][j]=0
else{
if((i==1&&j==1)||(i==18&&j==18)) /*因为距入口或出口一步的路是必经之路，故设该通道块为"0"加大迷宫能通行的概率*/
mg[i][j]=0
else
mg[i][j]=1
}
}
}
//构造一个空栈
Status InitStack(SqStack &s){
s.base =(SElemType *)malloc(stack_init_size * sizeof(SElemType))
if(!s.base) return OVERFLOW
s.top=s.base
s.stacksize=stack_init_size
return OK
}
//当前块可否通过
Status Pass(PosType e){
if (mg[e.x][e.y]==0) //0时可以通过
return OK // 如果当前位置是可以通过，返回1
return OVERFLOW// 其它情况返回0
}
//留下通过的足迹
Status FootPrint(PosType e){
mg[e.x][e.y]=7
return OK
}
//压入栈
Status Push(SqStack &s,SElemType e){
if(s.top-s.base>=s.stacksize){
s.base=(SElemType *)realloc(s.base,(s.stacksize+stack_increment) *sizeof(SElemType))
if(!s.base)exit(OVERFLOW)
s.top=s.base+s.stacksize
s.stacksize+=stack_increment
}
*s.top++=e
return OK
}
//出栈
Status Pop(SqStack &s,SElemType &e){
if(s.top==s.base)
return ERROE
e=*--s.top
return OK
}
//下一步
PosType NextPos(PosType &e,int dir){
PosType E
switch(dir){
case 1:E.x=e.x //向下
E.y=e.y+1
break
case 2:E.x=e.x+1//向右
E.y=e.y
break
case 3:E.x=e.x //向上
E.y=e.y-1
break
case 4:E.x=e.x-1//向左
E.y=e.y
break
}
return E
}
//是否空栈
Status StackEmpty(SqStack s){
if (s.top==s.base)
return OK
return OVERFLOW
}
//留下不能通过的足迹
Status MarkPrint(PosType e){
mg[e.x][e.y]=3
return OK
}
//迷宫函数
// 若迷宫maze中从入口 start到出口 end的通道，则求得一条存放在栈中
// （从栈底到栈顶），并返回TRUE；否则返回FALSE
Status MazePath(int mg,PosType start,PosType end,SqStack &s){
PosType curpos
InitStack(s)
SElemType e
int curstep
curpos=start// 设定"当前位置"为"入口位置"
curstep=1 // 探索第一步
do{
if(Pass(curpos)){ // 当前位置可通过，即是未曾走到过的通道块
FootPrint(curpos)// 留下足迹
e.di =1
e.ord = curstep
e.seat= curpos
Push(s,e)// 加入路径
if(curpos.x==end.x&&curpos.y==end.y){
printf("\n\n0∩_∩0 能到达终点!")
return TRUE
}
curpos=NextPos(curpos,1)// 下一位置是当前位置的东邻
curstep++ // 探索下一步
}
else{ // 当前位置不能通过
if(!StackEmpty(s)){
Pop(s,e)
while(e.di==4&&!StackEmpty(s)){
MarkPrint(e.seat)
Pop(s,e)
}
if(e.di<4){
e.di++
Push(s,e)// 留下不能通过的标记，并退回一步
curpos=NextPos(e.seat,e.di)/* 当前位置设为新方向的相邻块*/
}//if
}//if
}//else
}while(!StackEmpty(s))
printf("\n\n囧 ! 不能到达终点!")
return FALSE
}
//打印迷宫
void PrintMaze(){
int i,j
printf("运行路径:\n\n")
for(i=0i<20i++){
for(j=0j<20j++){
if(mg[i][j]==0)printf(" ")
else if(mg[i][j]==1) printf("■") //迷宫的"墙"
else if(mg[i][j]==3) printf("◇") //不通的路
else if(mg[i][j]==7)printf("○") //通过的路径
}
printf("\n")
}
printf("\n")
}
void main(){
SqStack S
PosType start,end
start.x=1start.y=0//起点坐标
end.x=18end.y=19//终点坐标
printf("\n==================迷宫游戏==================")
printf("\n说明:■不能走的区域\t◇走不通的区域")
printf("\n'空格'代表未到过的区域")
printf("\n ○代表能通过的路径，指向终点")
printf("\n============================================")
Random()
printf("\n\nTest 1:")
MazePath(mg[20][20],start,end,S)
PrintMaze()
system("pause")
Random()
printf("\nTest 2:")
MazePath(mg[20][20],start,end,S)
PrintMaze()
system("pause")
Random()
printf("\nTest 3:")
MazePath(mg[20][20],start,end,S)
PrintMaze()
printf("\n==========程序退出，感谢使用!==========\n")
}
#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()}
#include<iostream>using namespace std
class T //定义描述迷宫中当前位置的结构类型
{
public:
int x//x代表当前位置的行坐标
int y//y代表当前位置的列坐标
int dir//0:无效,1:东,2:南,3:西,4:北
}
class LinkNode //链表结点
{
friend class Stack
public:
T data
LinkNode *next
}
class Stack
{
private:
LinkNode *top//指向第一个结点的栈顶指针
public:
Stack()//构造函数，置空栈
~Stack()//析构函数
void Push(T e)//把元素data压入栈中
T Pop()//使栈顶元素出栈
T GetPop()//取出栈顶元素
void Clear()//把栈清空
bool empty()//判断栈是否为空，如果为空则返回1，否则返回0
}
Stack::Stack() //构造函数，置空栈
{
top=NULL
}
Stack::~Stack() //析构函数
{
}
void Stack::Push(T e) //把元素x压入栈中
{
LinkNode *P
P=new LinkNode
P->data=e
P->next=top
top=P
}
T Stack::Pop() //使栈顶元素出栈
{
T Temp
LinkNode *P
P=top
top=top->next
Temp=P->data
delete P
return Temp
}
T Stack::GetPop() //取出栈顶元素
{
return top->data
}
void Stack::Clear() //把栈清空
{
top=NULL
}
bool Stack::empty() //判断栈是否为空，如果为空则返回1，否则返回0
{
if(top==NULL) return 1
else return 0
}
int move[4][2]={{0,1},{1,0},{0,-1},{-1,0}}//定义当前位置移动的4个方向
bool Mazepath(int **maze,int m,int n)
//寻找迷宫maze中从（0，0）到（m,n）的路径
//到则返回true,否则返回false
void PrintPath(Stack p)//输出迷宫的路径
void Restore(int **maze,int m,int n)//恢复迷宫
int** GetMaze(int &m,int &n)//获取迷宫
//返回存取迷宫的二维指针
int main()
{
int m=0,n=0//定义迷宫的长和宽
int **maze//定义二维指针存取迷宫
maze=GetMaze(m,n)//调用GetMaze(int &m,int &n)函数，得到迷宫
if(Mazepath(maze,m,n)) //调用Mazepath(int **maze,int m,int n)函数获取路径
cout<<"迷宫路径探索成功!\n"
else cout<<"路径不存在!\n"
return 0
}
int** GetMaze(int &m,int &n)//返回存取迷宫的二维指针
{
int **maze//定义二维指针存取迷宫
int i=0,j=0
cout<<"请输入迷宫的长和宽:"
int a,bcin>>a>>b//输入迷宫的长和宽
cout<<"请输入迷宫内容:\n"
m=a
n=b//m,n分别代表迷宫的行数和列数
maze=new int *[m+2]//申请长度等于行数加2的二级指针
for(i= 0i<m+2i++) //申请每个二维指针的空间
{
maze[i]=new int[n+2]
}
for(i=1i<=mi++) //输入迷宫的内容，0代表可通，1代表不通
for(j=1j<=nj++)
cin>>maze[i][j]
for(i=0i<m+2i++)
maze[i][0]=maze[i][n+1]=1
for(i=0i<n+2i++)
maze[0][i]=maze[m+1][i]=1
return maze//返回存贮迷宫的二维指针maze
}
bool Mazepath(int **maze,int m,int n)//寻找迷宫maze中从（0，0）到（m,n）的路径
//到则返回true,否则返回false
{
Stack q,p//定义栈p、q,分别存探索迷宫的过程和存储路径
T Temp1,Temp2
int x,y,loop
Temp1.x=1
Temp1.y=1
q.Push(Temp1)//将入口位置入栈
p.Push(Temp1)
maze[1][1]=-1//标志入口位置已到达过
while(!q.empty()) //栈q非空，则反复探索
{
Temp2=q.GetPop()//获取栈顶元素
if(!(p.GetPop().x==q.GetPop().x&&p.GetPop().y==q.GetPop().y))
p.Push(Temp2)
//如果有新位置入栈，则把上一个探索的位置存入栈p
for(loop=0loop<4loop++) //探索当前位置的4个相邻位置
{
x=Temp2.x+move[loop][0]//计算出新位置x位置值
y=Temp2.y+move[loop][1]//计算出新位置y位置值
if(maze[x][y]==0) //判断新位置是否可达
{
Temp1.x=x
Temp1.y=y
maze[x][y]=-1//标志新位置已到达过
q.Push(Temp1)//新位置入栈
}
if((x==(m))&&(y==(n))) //成功到达出口
{
Temp1.x=m
Temp1.y=n
Temp1.dir=0
p.Push(Temp1)//把最后一个位置入栈
PrintPath(p)//输出路径
Restore(maze,m,n)//恢复路径
return 1//表示成功找到路径
}
}
if(p.GetPop().x==q.GetPop().x&&p.GetPop().y==q.GetPop().y)
//如果没有新位置入栈，则返回到上一个位置
{
p.Pop()
q.Pop()
}
}
return 0//表示查找失败，即迷宫无路经
}
void PrintPath(Stack p) //输出路径
{
cout<<"迷宫的路径为\n"
cout<<"括号内的内容分别表示为(行坐标,列坐标,数字化方向,方向)\n"
Stack t//定义一个栈，按从入口到出口存取路径
int a,b
T data
LinkNode *temp
temp=new LinkNode//申请空间
temp->data=p.Pop()//取栈p的顶点元素，即第一个位置
t.Push(temp->data)//第一个位置入栈t
delete temp//释放空间
while(!p.empty()) //栈p非空，则反复转移
{
temp=new LinkNode
temp->data=p.Pop()//获取下一个位置
//得到行走方向
a=t.GetPop().x-temp->data.x//行坐标方向
b=t.GetPop().y-temp->data.y//列坐标方向
if(a==1) temp->data.dir=1//方向向下，用1表示
else if(b==1) temp->data.dir=2//方向向右，用2表示
else if(a==-1) temp->data.dir=3//方向向上，用3表示
else if(b==-1) temp->data.dir=4//方向向左，用4表示
t.Push(temp->data)//把新位置入栈
delete temp
}
//输出路径，包括行坐标，列坐标，下一个位置方向
while(!t.empty()) //栈非空，继续输出
{
data=t.Pop()
cout<<'('<<data.x<<','<<data.y<<','<<data.dir<<","//输出行坐标，列坐标
switch(data.dir) //输出相应的方向
{
case 1:cout<<"↓)\n"break
case 2:cout<<"→)\n"break
case 3:cout<<"↑)\n"break
case 4:cout<<"←)\n"break
case 0:cout<<")\n"break
}
}
}
void Restore(int **maze,int m,int n) //恢复迷宫
{
int i,j
for(i=0i<m+2i++) //遍历指针
for(j=0j<n+2j++)
{
if(maze[i][j]==-1) //恢复探索过位置，即把-1恢复为0
maze[i][j]=0
}
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）