用数据结构 C++ 编写 迷宫

Question

迷宫有两个门，一个叫做入口，一个叫做出口。把一个老鼠从一个无顶盖的大盒子的入口赶进迷宫。迷宫中设置很多隔壁。对前进的方向形成了多处障碍，在迷宫的唯一出口处放置了一块奶酪，吸引老鼠在迷宫中寻找通路以达到出口。求解迷宫问题，即找从入口到出口的路径。

Answer 1

#include<stdio.h>
#define M 8
#define N 8
#define MaxSize 100
int mg[M+2][N+2]={
,
,
,
,
,
,
,
,
,

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

栈或者队列都行。
也就是深度优先搜索或者广度优先搜索。
就是站在一个点向四个方向走（假如没障碍的话）。