#include<iostream>
using namespace std
{
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
}
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个方向
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
}
}
int** GetMaze(int &m,int &n)//返回存取迷宫的二维指针
{
int **maze//定义二维指针存取迷宫
int i=0,j=0
cout<<"请输入迷宫的长和宽:"
int a,bcin>>a>>b//输入迷宫的长和宽
cout<<"请输入迷宫内容:(0为通路，1为墙)\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）的路径
{
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//表示查找失败，即迷宫无路经
}
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
}
输入数据：
搜索的路径为：
#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条）