毫无头绪的数据结构（C++）迷宫问题 寻求好的解决方案。。。主要问题是他干嘛要用队列？

发布网友 发布时间：2023-01-11 04:53

我来回答

共2个回答

热心网友 时间：2023-10-27 12:00

#include<stdio.h>
#define M 8
#define N 8
#define MaxSize 100
int mg[M+2][N+2]={
{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}
};
struct
{
int i;int j;int di;
}Stack[MaxSize],Path[MaxSize];
int top=-1;
int count=1;
int minlen=MaxSize;
void mgpath()
{
int i,j,di,find,k;
top++;Stack[top].i=1;Stack[top].j=1;Stack[top].di=-1;mg[1][1]=-1;

while(top>-1)
{
i=Stack[top].i;
j=Stack[top].j;
di=Stack[top].di;
if(i==M && j==N)
{
printf("%8d: ",count++);
for(k=0;k<=top;k++)
{
printf("(%d,%d) ",Stack[k].i,Stack[k].j);
if((k+1)%10==0)printf("\n\t ");
}
printf("\n");
if(top+1<minlen)
{
for(k=0;k<=top;k++)
Path[k]=Stack[k];
minlen=top+1;
}
mg[Stack[top].i][Stack[top].j]=0;
top--;
i=Stack[top].i;
j=Stack[top].j;
di=Stack[top].di;
}
find=0;
while(di<8 && find==0)
{
di++;
switch(di)
{
case 0:i=Stack[top].i-1;j=Stack[top].j;break;
case 1:i=Stack[top].i;j=Stack[top].j+1;break;
case 2:i=Stack[top].i+1;j=Stack[top].j;break;
case 3:i=Stack[top].i;j=Stack[top].j-1;break;
}
if(mg[i][j]==0)find=1;
}
if (find==1)

{ Stack[top].di=di;
top++;
Stack[top].i=i;
Stack[top].j=j;
Stack[top].di=-1;
mg[i][j]=-1;
}
else
{
mg[Stack[top].i][Stack[top].j]=0;
top--;
}
}
printf("最短路径如下：\n");
printf("长度： %d\n",minlen);
printf("路径: ");
for(k=0;k<minlen;k++)
{
printf("(%d,%d) ",Path[k].i,Path[k].j);
if((k+1)%10==0)printf("\n\t");
}
printf("\n");
}
void main()
{
printf("迷宫所有路径如下:\n");
mgpath();
}

热心网友 时间：2023-10-27 12:01

http://wenku.baidu.com/view/483d2fdc5022aaea998f0f88.html

参考资料：http://wenku.baidu.com/view/483d2fdc5022aaea998f0f88.html