迷宫的另一种解法[非递归]

关于迷宫，有一个引人入胜的希腊神话，这也是为什么现今每当人们提到这个问题，总是兴致勃勃（对于年青人，估计是RPG玩多了），正如虽然九宫图连小学生都能做出来，我们总是自豪的说那叫“洛书”。这个神话我不复述了，有兴趣的可以在搜索引擎上输入“希腊神话 迷宫”，就能找到很多的介绍。

迷宫的神话讲述了一位英雄如何靠着“线团”杀死了牛头怪（玩过《英雄无敌》的朋友一定知道要想造牛头怪，就必须建迷宫，也是从这里来的），我看到的一本编程书上援引这段神话讲述迷宫算法的时候，不知是有意杜撰，还是考证不严，把这个过程叙述成：英雄靠着线团的帮助——在走过的路上铺线，每到分岔口向没铺线的方向前进，如果遇到死胡同，沿铺的线返回，并铺第二条线——走进了迷宫深处，杀死了牛头怪。然而，神话传说讲的是，英雄被当成贡品和其他的孩子送到了迷宫的深处，英雄杀死了牛头怪，靠着线团标识的路线退出了迷宫。实际上，这个线团只是个“栈”，远没有现代人赋予给它的“神奇作用”。我想作者也是RPG玩多了，总想着怎样“勇者斗恶龙”，然而，实际上却是“胜利大逃亡”。

迷宫问题实际上是一个心理测试，它反映了测试者控制心理稳定的能力——在一次次失败后，是否失去冷静最终陷在迷宫之中，也正体现了一句诗，“不识庐山真面目，只缘身在此山中”。换而言之，我们研究迷宫的计算机解法，并没有什么意义，迷宫就是为人设计的，而不是为机器设计的，它之所以称为“迷”宫，前提是人的记忆准确性不够高；假设人有机器那样的准确的记忆，只要他不傻，都能走出迷宫。现在可能有人用智能机器人的研究来反驳我，实际上，智能机器人是在更高的层面上模拟人的思考过程，只要它完全再现了人的寻路过程，它就能走出迷宫。但是，研究迷宫生成的计算机方法，却是有意义的，因为人们总是有虐待自己的倾向（不少人在RPG里的迷宫转了三天三夜也不知道疲倦），呵呵，笑谈。

不管怎么说，还是亲自研究一下计算机怎么走迷宫吧。

迷宫的存储

按照惯例，用一个二维数组来表示迷宫，0表示墙，1表示通路，以后我们的程序都走下面这个迷宫。

打个比方吧，递归法好比是一个军队要通过一个迷宫，到了第一个分岔口，有3条路，将军命令3个小队分别去探哪条路能到出口，3个小队沿着3条路分别前进，各自到达了路上的下一个分岔口，于是小队长再分派人手各自去探路——只要人手足够（对照而言，就是计算机的堆栈足够），最后必将有人找到出口，从这人开始只要层层上报直属领导，最后，将军将得到一条通路。所不同的是，计算机的递归法是把这个并行过程串行化了。

而回溯法则是一个人走迷宫的思维模拟——他只能寄希望于自己的记忆力，如果他没有办法在分岔口留下标记（电视里一演到什么迷宫寻宝，总有恶人去改好人的标记）。

想到这里突然有点明白为什么都喜欢递归了，他能够满足人心最底层的虚荣——难道你不觉得使用递归就象那个分派士兵的将军吗？想想汉诺塔的解法，也有这个倾向，“你们把上面的N－1个拿走，我就能把下面的挪过去，然后你们在把那N－1个搬过来”。笑谈，切勿当真。

这两种方法的例程，我不给出了，网上很多。我只想对书上的递归解法发表点看法，因为书上的解法有偷梁换柱的嫌疑——迷宫的储存不是用的二维数组，居然直接用岔路口之间的连接表示的——简直是人为的降低了问题的难度。实际上，如果把迷宫抽象成（岔路口）点的连接，迷宫就变成了一个“图”，求解入口到出口的路线，完全可以用图的遍历算法来解决，只要从入口DFS到出口就可以了；然而，从二维数组表示的迷宫转化为图是个很复杂的过程。并且这种转化，实际上就是没走迷宫之前就知道了迷宫的结构，显然是不合理的。对此，我只能说这是为了递归而递归，然后还自己给自己开绿灯。

但迷宫并不是只能用上面的方法来走，前提是，迷宫只要走出去就可以了，不需要找出一条可能上的最短路线——确实，迷宫只是前进中的障碍，一旦走通了，没人走第二遍。下面的方法是一位游戏玩家提出来的，既不需要递归，也不需要栈来回溯——玩游戏还是有收获的。

我在迷宫中用粗线描出的路线，实际上，在迷宫中，只要从入口始终沿着一边的墙走，就一定能走到出口，那位玩家称之为“靠一边走”——如果你不把迷宫的通路看成一条线，而是一个有面积的图形，很快你就知道为什么。编程实现起来也很简单。

下面的程序在TC2中编译，不能在VC6中编译——为了动态的表现人的移动情况，使用了gotoxy()，VC6是没有这个函数的，而且堆砌迷宫的219号字符是不能在使用中文页码的操作系统的32位的console程序显示出来的。如果要在VC6中实现gotoxy()的功能还得用API，为了一个简单的程序没有必要，所以，就用TC2写了，突然换到C语言还有点不适应。

#include <stdio.h>

typedef struct hero {int x,y,face;} HERO;

void set_hero(HERO* h,int x,int y,int face){h->x=x;h->y=y;h->face=face;}

void go(HERO* h){if(h->face%2) h->x+=2-h->face;else h->y+=h->face-1;}

void goleft(HERO* h){if(h->face%2) h->y+=h->face-2;else h->x+=h->face-1;}

void turnleft(HERO* h){h->face=(h->face+3)%4;}

void turnright(HERO* h){h->face=(h->face+1)%4;}

void print_hero(HERO* h, int b)

{

gotoxy(h->x + 1, h->y + 1);

if (b)

{

switch (h->face)

{

case 0: printf("%c", 24); break;

case 1: printf("%c", 16); break;

case 2: printf("%c", 25); break;

case 3: printf("%c", 27); break;

default: break;

}

}

else printf(" ");

}

int maze[10][10] =

{

0, 0, 0, 1, 0, 0, 0, 1, 0, 0,

1, 0, 1, 1, 0, 1, 1, 1, 1, 0,

1, 0, 0, 0, 0, 0, 0, 0, 0, 0,

0, 0, 1, 0, 1, 1, 0, 1, 1, 1,

0, 0, 1, 0, 1, 1, 0, 0, 0, 1,

1, 0, 1, 0, 1, 1, 0, 1, 0, 1,

0, 0, 1, 0, 1, 1, 0, 1, 0, 1,

0, 1, 1, 0, 0, 0, 0, 1, 0, 1,

0, 0, 0, 0, 1, 0, 1, 1, 0, 1,

0, 1, 1, 1, 1, 0, 0, 0, 0, 0

};

void print_maze()

{

int i, j;

for (i = 0; i < 10; i++)

{

for (j = 0; j < 10; j++)

{

if (maze[i][j]) printf("%c", 219);

else printf(" ");

}

printf("\n");

}

}

int gomaze(HERO* h)

{

HERO t = *h; int i;

for (i = 0; i < 2; t = *h)

{

print_hero(h, 1); sleep(1); go(&t);

if (t.x >= 0 && t.x < 10 && t.y >= 0 && t.y < 10 && !maze[t.y][t.x])

{

print_hero(h, 0); go(h);/*前方可走则向前走*/

if (h->x == 9 && h->y == 9) return 1; goleft(&t);

if (h->x == 0 && h->y == 0) i++;

if (t.x >= 0 && t.x < 10 && t.y >= 0 && t.y < 10 && !maze[t.y][t.x]) turnleft(h);/*左方无墙向左转*/

}

else turnright(h);/*前方不可走向右转*/

}

return 0;

}

main()

{

HERO Tom;/*有个英雄叫Tom*/

set_hero(&Tom, 0, 0, 0);/*放在(0,0)面朝北*/

clrscr();

print_maze();

gomaze(&Tom);/*Tom走迷宫*/

}

运行结果演示如下图：

总结

书上讲的基本上就这些了，要是细说起来，几天几夜也说不完。前面我并没有讲如何写递归算法，实际上给出的都是非递归的方法，我也觉得有点文不对题。我的目的是使大家明白，能写出什么算法，主要看你解决问题的指导思想，换而言之，就是对问题的认识程度。所以初学者现在就去追求“漂亮”的递归算法，是不现实的，结果往往就是削足适履，搞的一团糟——有位仁兄写了个骑马游世界的“递归”程序，在我机器上10分钟没反映。其实优秀的递归算法是在对问题有了清楚的认识后才会得出的。