王文霞

（运城学院计算机科学与技术系，山西　044000）

基于路径标记法的迷宫问题求解

王文霞

（运城学院计算机科学与技术系，山西044000）

0　引言

迷宫问题在我们的生活中常常遇到，例如我们顺着某一方向向前进行探索，遇到岔口，则要选择某一路口继续前进，这样会出现两种情况：若能走通，继续前进，直到出口；否则沿原路退回，选择另一方向继续探索，直到所有通路都探索到为止。国内外许多学者对迷宫问题进行了研究，从LEE算法开始有了很多不同的迷宫求解的改进方法［1-2］。本文中，利用递归函数visit（）用”2”标记搜索过程中的位置，可方便求得复杂迷宫的解；同时为了使迷宫中每个点判断都有四个方向，在生成的迷宫外围增加了一圈用1表示的墙［3-4］。例如图1所示的用一个二维数组A［8，10］的矩阵表示的迷宫，下标从（0,0）开始。其中，图中0表示通道，1表示障碍物，左上角（1，1）为入口，右下角（6，8）为出口。

图1　8×10的矩阵

1　算法思想

此算法采用（0，1）组成的矩阵模拟复杂迷宫，通路用◇表示，障碍用■表示，调用visit（）函数，求出从入口（1，1）到出口（6，8）所有路径，最后对矩阵中的所有路径进行递增排序且进行了二次转化，并显示出运行结果。

2　算法步骤

（1）在txt文档中任意输入一个由0、1组成的矩阵（也可通过随机函数生成矩阵）；

（2）调用文件函数fopen（）打开用矩阵表示的迷宫；

（3）转换迷宫；迷宫中除外围墙外，所有迷宫中的1用□表示，迷宫中的0用■表示，转换后的图如图2所示。

图2　迷宫转换图

（4）从入口a（1，1）开始，依次对a［i］［j+1］、a［i+1］［j］、a ［i］［j-1］、a［i-1］［j］四个方向调用visit（）递归函数进行判断，如能走通则把相对应位置置成2，直到走到迷宫出口a［6］［8］即表示迷宫有一条路径，把此矩阵作为一个数组元素放在maze数组中，jilu++表示路径条数加1。……