#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;
}