假期连载之五
（迷宫Maze的魅力——一个初级迷宫解法的讨论及延伸A）
现在，我们根据以上连载中的内容来研究一个有趣的应用问题。
假设在一个二位数组maze[m+2][p+2]表示的迷宫中，除maze[1][0]以及maze[m][p+1]分别表示入口、出口外，包括第0、m+1行、第0、p+1列的元素均表示迷宫的围墙，用1表示，其它元素同样用1表示围墙，0表示通路，如下图例：
1 1 1 1 1 1
0 0 1 1 0 1
1 0 0 1 1 1
1 1 0 1 0 1
1 0 1 0 0 0
1 1 1 1 1 1
以上是一个6*6的迷宫图示，其中(1,0)和(4,5)表示了迷宫的出口和入口。对于迷宫中除边界外的任意元素maze[i][j]，有0<i<m，0<j<p，并且当maze[i][j]==0时路通，maze[i][j]==1时不通。我们假设迷宫中的个体一次可移动八个方向——N，NE，E，SE，S，SW，W，NW，其数据关系据此可知。我们先根据可前进的方向建立一个前进方向表，给出各个方向的偏移量。
struct offsets
{
int a,b; //a、b分别表示在x和y方向上的偏移量。
char *dir; //dir为方向。
};
offsets move[8]; //各个方向的偏移量表。
在使用上述数据结构时，需要初始化move[8]中８个方向的元素值，如果该前进方向走不通，则在前进路径上回退一步，再尝试其他的允许方向。
同时为了防止重走原路，另外设置一个标志矩阵mark[m+2][p+2]，它的所有元素都初始化为０，一旦进行到迷宫的某个位置[i][j]，则将mark[i][j]置为1，下次这个位置则被屏蔽。下面给出解决迷宫问题的递归算法C++语言描述：
int SeekPath(int x,int y)
//在本例中我们首先从Maze[1][1]开始探索，如果找到出口则返回1，否则返回0;
{
int i,g,h;
char *d; //g,h记录位置信息，dir记录方向
if(x==n&&y==p)
return 1;
for(i=0;i<8;i++) //每次选择一个方向探索
{
g=x+move[i].a;
h=y+move[i].b;
d=move[i].dir;
if(Maze[g][h]==0&&mark[g][h]==0)
{
mark[g][h]=1;
if(SeekPath(g,h)) //选择此位置递归探索
{
cout<<”(”<<g<<”,”<<h<<”),”<<”Direction ”<<dir<<endl;
//此处输出路径的顺序是逆向的
return 1;
}
}
}
if(x==1&&y==1)
cout<<”no path in Maze”<<endl;
return 0;
}
我们将上述迷宫数据经由此算法检查，g++给出了如下输出：
(4,4),Direction W
(4,5),Direction SE
(3,4),Direction NE
(4,3),Direction SE
(3,2),Direction S
(2,2),Direction SE
(1,1),Direction E
由于算法本身的问题，输出逻辑上存在一些偏差，但并不影响其正确性。
现在，我们对递归算法作出一些改进，使其能通过栈处理的方式提高算法性能。为了达到这一目标，我们需要设置一个三元组来存储已走过路径的信息，如下所示：
struct items
{
int x,y,dir; //位置和前进方向的序号
}
此算法的原理是，我们对当前位置的信息进行记录并压栈，按照前进方向表给出的数据向某一个允许的方向前进一位，并将此位置压栈，继续进行上述过程。如果当前位置无法走通，则将前进方向退栈，并在前进路径上回退一步，并尝试其它方向，如果栈空则表示已回退到开始位置。
下面给出迷宫非递归算法的C++描述，需要提前说明的是，我们已假设存在一个完整的Stack类，并具备连载四包含的所有栈操作函数。
int path(int m,int p) //关于参数的介绍请借鉴上例
{
int i,j,d,g,h;
mark[1][0]=1; //假定(1,0)为入口
Stack<items>st(m*p); //初始化栈st，其大小为m*p，这是根据迷宫空间设置的最大可能值。
items tmp; //选择当前位置信息
tmp.x=1;
tmp.y=0;
tmp.dir=2;
st.Push(tmp); //将初始位置压栈
while(st.IsEmpty()==FALSE)
{
st.Pop(tmp); //将栈顶位置信息弹出，并设置为当前位置
i=tmp.x;
j=tmp.y;
d=tmp.dir;
while(d<8) //选择前进方向
{
g=i+move[d].a;
h=j+move[d].b;
if(g==m&&h==p)
{//已找到出口
cout<<st;
//这里在Stack类的内部重载了操作符<<，用于输出st中保存的路径
cout<<m<<” “<<p<<endl;
return;
}
if(Maze[g][h]==0&&mark[g][h]==0)
{//选择新的可通位置并前进
mark[g][h]=1;
tmp.x=i;
tmp.y=j;
tmp.dir=d;
st.Push(tmp);
i=g;
j=h;
d=0;
}
else d++;
}
cout<<”no path Maze”<<endl;
}
};
在上述算法中，由于涉及到了栈的操作，可能会使算法难度增加，但事实证明其在性能及智能化的扩展方面存在很大的提高。对于小型、简单的二维迷宫，均可根据以上算法对其进行有效的处理。
在今后涉及到树或图部分的内容时，我们将再次回顾迷宫Maze问题，届时的迷宫实例将具备更多复杂的元素以及更巧妙的规则，使当前的算法复杂度大幅提高，也不仅仅是一般数据结构或算法就能够轻松解决的。
(未完待续)