Question

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

使用顺序队列求迷宫的最短路径
1、在给定的存储结构和空间大小的条件下，定义队列的初始化函数；
2、在少用一个单元的条件下定义队列的入队函数；
3、定义队列的出队函数；
4、定义判断队空函数；
5、定义销毁队列函数；
6、使用顺序队列求迷宫的最短路径。

数据输入与输出要求
输入示例：
4 4
S...
....
....
...D
3 4
S.X.
.XX.
...D
4 4
SX..
.X..
.X..
.X.D
0 0 0

输出示例：
4
5
NO
(注：第一行输入的数据表示迷宫的数据规模n（1<n<=50）行m（1<m<=50）列，S是出发点，D是迷宫的出口，.号表示通路，X表示墙体不通，输出的数据表示从入口到出口最少需要走k步或没有通路，)

Answer 1

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

Answer 2

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