#include "stdafx.h"
#include
#include"malloc.h"
int mg[6][6]={
{1,1,1,1,1,1},
{1,0,0,0,1,1},
{1,0,1,0,0,1},
{1,0,0,0,1,1},
{1,1,0,0,0,1},
{1,1,1,1,1,1}
};
typedef struct node
{
int i;
int j;
int next;
struct node pnext;
}Grid;
typedef struct
{
int len;
Grid *front,*rear;
}Route;
Route r1={0,NULL,NULL};
Route r2={6*6,NULL,NULL};
int count=0;
void EnQueue(int i,int j,Route *r);
void DeleteRear(Route *r);
void DispQueue(Route *q);
void ClearQueue(Route *q);
void CopyQueue(Route *r1,Route *r2);
void GetRoute(int i,int j,int xi,int xj);
int main(int argc, char argv[])
{
printf("迷宫阵路径如下:\n");
GetRoute(1,1,4,4);
printf("最短路径如下");
DispQueue(&r2);
return 0;
}
void EnQueue(int i,int j,Route r)
{
Grid *p;
p=(Grid)malloc(sizeof(Grid));
p->i=i;
p->j=j;
p->next=-1;
p->pnext=NULL;
if(r->front==NULL)
{
r->front=p;
r->rear=p;
}
else
{
r->rear->pnext=p;
r->rear=p;
}
r->len++;
}
void DeleteRear(Route r)
{
Grid *pre=NULL;
Grid *p=r->front;
while(p!=r->rear)
{
pre=p;
p=p->pnext;
}
if(r->rear!=NULL)
{
free(r->rear);
r->len--;
if(pre==NULL)
{
r->front=r->rear=NULL;
}
}
else
{
pre->pnext=NULL;
r->rear=pre;
}
}
void DispQueue(Route *q)
{
Grid *p=q->front;
int cnt=0;
while(p!=NULL)
{
printf("(%d,%d)",p->i,p->j);
if(++cnt==10)
{
printf("\n");
cnt=0;
}
p=p->pnext;
}
printf("此路径长度为%d",q->len);
}
void ClearQueue(Route *q)
{
Grid*p,*r;
p=q->front;
q->front=q->rear=NULL;
q->len=0;
while(p!=NULL)
{
r=p->pnext;
free(p);
p=r;
}
}
void CopyQueue(Route *r1,Route *r2)
{
Grid *p;
Grid *q=r1->front;
while(q!=NULL)
{
p=(Grid)malloc(sizeof(Grid));
p->i=q->i;
p->j=q->j;
p->pnext=NULL;
if(r2->front==NULL)
{
r2->front=r2->rear=p;
}
else
{
r2->rear->pnext=p;
r2->rear=p;
}
q=q->pnext;
}
r2->len=r1->len;
}
void GetRoute(int i,int j,int xi,int xj)
{
int ai,bj,next,find;
ai=i;
bj=j;
EnQueue(ai,bj,&r1);
mg[ai][bj]=-1;
while(r1.rear!=NULL)
{
ai=r1.rear->i;
bj=r1.rear->j;
next=r1.rear->next;
if(ai==xi&&bj==xj)
{
printf("第%d条路径",count++);
DispQueue(&r1);
printf("\n");
if(r1.len {
ClearQueue(&r2);
CopyQueue(&r1,&r2);
}
mg[r1.rear->i][r1.rear->j]=0;
DeleteRear(&r1);
ai=r1.rear->i;
bj=r1.rear->j;
next=r1.rear->next;
}
find=0;
while(next {
next++;
switch(next)
{
case 0: ai=r1.rear->i-1;bj=r1.rear->j;break;
case 1: ai=r1.rear->i;bj=r1.rear->j+1;break;
case 2: ai=r1.rear->i+1;bj=r1.rear->j;break;
case 3: ai=r1.rear->i;bj=r1.rear->j-1;break;
}
if(mg[ai][bj]==0)
{
find=1;
}
}
if(find==1)
{
r1.rear->next=next;
EnQueue(ai,bj,&r1);
mg[r1.rear->i][r1.rear->j]=-1;
}
else
{
mg[r1.rear->i][r1.rear->j]=0;
DeleteRear(&r1);
}
}
}