迷宫算法,求解所有路径(DFS),(bug找了好久 )
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了迷宫算法,求解所有路径(DFS),(bug找了好久 ),小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2174字,纯文字阅读大概需要4分钟。
内容图文
![迷宫算法,求解所有路径(DFS),(bug找了好久 )](/upload/InfoBanner/zyjiaocheng/718/a129251096bf44a9914885b316d1ecc6.jpg)
#include
using namespace std;
typedef class maps
{
public :
int x;
int y;
int d;
maps *next;
}*LinkStack,Link;
const int M=10,N=10;
int cx=8,cy=8;//定义出口变量
void push(LinkStack &L,int i,int j,int di);
void pop(LinkStack &L);
void init_LinkStack(LinkStack &L);
int counts(LinkStack &L);
int main()
{
int a[M][N]={
{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}
};
LinkStack L;
init_LinkStack(L);
LinkStack p=L->next;
LinkStack s;
LinkStack q;
LinkStack temp=new Link;
temp->next=NULL;
int num=0,di,founds=0;
int ix=1,jy=1;
int i,j;
int sizes=1000;//定义一个记录最短步数的变量
while(p!=NULL)
{
di=p->d;
if(ix==8&&jy==8)
{
if(counts(L)<sizes)
{
sizes=counts(L);
q=temp->next;
while(q!=NULL)
{
pop(temp);
q=q->next;
}
temp->next=NULL;
while(p!=NULL)
{
s=new Link;
s->x=p->x;
s->y=p->y;
s->d=p->d;
s->next=temp->next;
temp->next=s;
p=p->next;
}
p=L->next;
num=0;
q=temp->next;
while(q!=NULL)
{
cout<<"("<<q->x<<","<<q->y<<")"<<" ";
num++;
if(num%5==0)
{
cout<<endl;
}
q=q->next;
}
cout<<endl<<endl<<"*****"<<endl;
q=temp->next;
}
a[ix][jy]=0;
pop(L);
p=L->next;
ix=p->x;
jy=p->y;
di=p->d;
}
else
{
di++;
founds=0;
while(di<4)
{
switch(di)
{
case 0:
i=ix-1;
j=jy;
break;
case 1:
i=ix;
j=jy+1;
break;
case 2:
i=ix+1;
j=jy;
break;
case 3:
i=ix;
j=jy-1;
break;
}
if(a[i][j]==0)
{
founds=1;
ix=i;
jy=j;
push(L,ix,jy,di);
p=L->next;
a[ix][jy]=-1;
p->d=-1;
break;
}
else
{
di++;
}
}
if(founds==0)
{
pop(L);
p=L->next;
if(p==NULL)//这里一定要注意,指针是空的以后,不能再去赋值
{
goto tql;
}
a[ix][jy]=0;
ix=p->x;
jy=p->y;
}
}
}
tql:
{
cout<<"最短路径为"<<sizes<<endl;
q=temp->next;
num=0;
while(q!=NULL)
{
cout<<"("<<q->x<<","<<q->y<<") ";
num++;
q=q->next;
if(num%5==0)
{
cout<<endl;
}
}
}
}
void push(LinkStack &L,int i,int j,int di)
{
LinkStack s=new Link;
LinkStack p=L->next;
p->d=di;
s->x=i;
s->y=j;
s->next=L->next;
L->next=s;
}
void pop(LinkStack &L)
{
if(L->next==NULL)
{
return ;
}
else
{
LinkStack p=L->next;
L->next=p->next;
delete(p);
}
}
void init_LinkStack(LinkStack &L)
{
L=new Link;
L->next=NULL;
LinkStack s=new Link;
s->x=1;
s->y=1;
s->d=-1;
s->next=L->next;
L->next=s;
}
int counts(LinkStack &L)
{
int i=0;
LinkStack p=L->next;
while(p!=NULL)
{
i++;
p=p->next;
}
return i;
}
内容总结
以上是互联网集市为您收集整理的迷宫算法,求解所有路径(DFS),(bug找了好久 )全部内容,希望文章能够帮你解决迷宫算法,求解所有路径(DFS),(bug找了好久 )所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。