===》点我返回目录《===

我们都走过迷宫，在弯弯曲曲的小道上寻找出口，迷茫中夹带惊喜。刚开头都是乱走，碰到死胡同后又折回来，慢慢地有了一套办法，确保不遗漏可能的路径，还有些人知道使用左手/右手法则。

我们用程序来走走迷宫。我们这儿定义的迷宫是简单形式的，一个N*N矩形，四周有外墙，有一个入口，一个出口，保证有解，可以走的范围从[0,0]到[N-1,N-1]，假定[0,0]为入口，[N-1,N-1]为出口。

计算机里面，我们可以采用不遗漏可能路径的办法，就是深度优先搜索。作为预备知识，先介绍一下深度优先搜索和广度优先的概念。

深度优先搜索DFS的思路是从起点开始，对每一个可能的分支路径深入到不能再深入为止。而广度优先搜索BFS的思路是从起点开始，先把临近的节点走完，再对临近节点同样走。比如：

我们对上面的图，如何一个不漏地数出来？

按照深度优先，从a开始，接下来是临近点b，然后对b同样操作，到d，再到e。最后成为一个串：abdeghicf。

按照广度优先，从a开始，接下来是b，然后下一格临近点c，这样第一层的临近点走完了，就对b和c同样操作。最后成为一个串：abcdefghi。

详细的讨论在讲到数据结构的时候再说。

深度优先搜索是一种思路，保证一个不漏，其实是一种很笨的办法，但是很有用，因为经常会碰到没有什么好办法的场景，我们就利用计算机的快进行穷举搜索。我们具体编程也有不同的选择，下面介绍递归的办法进行实现。

我们先看怎么定义迷宫。我们认为迷宫是一个N*N格的矩形，有墙有空，我们可以用二维数组表格这些格，1表示墙，不能走，0表示空，可以走。假定左上角为入口，右下角为出口。

在Python中，定义二维数组不难，但是有小小的陷阱在其中。最直接的定义办法是array2=[[0,0,0],[0,0,0],[0,0,0]]，这样给出一个3*3的二维数组。但是作为一个有脸面的程序员，一般不会这么写程序，总是不想这么写死，而是想着用更加通用的方式。这个二维数组里面的一维数组是[0,0,0]，可以缩写成array2=[[0]*3,[0]*3,[0]*3]。再看一下，这三个一维数组都是一样的嘛，所以就会进一步缩写成array2=[[0]*3]*3。

注意了，陷阱来了，上面看似定义好了一个3*3的二维数组，你现在给它赋值：array2[0][0]=1，再看二维数组内容，竟然成了：[[1, 0, 0], [1, 0, 0], [1, 0, 0]]。每一个一维数组的第一个数都成了1。这就要用引用与值来解释了，一维数组本身是对象引用，*3会解释成把[0,0,0]这个一维数组引用三遍，修改它的值，别的引用都变了。

正确的定义方式是array2= [ [0] * 3 for i in range(3)]。所以，我们这样定义一个6*6的迷宫：

Mazewidth = 6Maze = [[0] * (Mazewidth) for i in range(Mazewidth)]

我们程序还要用一个同样的数组来记录走过的路径。Route = [[0] * (Mazewidth) for i in range(Mazewidth)]。我们反过来，用1表示走过的路径。

深度优先很好理解，相当于用临近节点替换当前节点继续操作下去。过程为：

（1） 从入口节点开始，设为当前状态；

（2） 按照一定次序（右下左上）选择到下一个节点，新节点设为当前状态，递归；

（3） 判断当前状态是否和前面的重复，如果重复则回到上一个状态，按照一定次序（右下左上）产生它的另一状态；

（4） 判断当前状态是否为目标状态，如果是目标，则找到一个解答，结束算法。

我们用一个递归函数move(Maze,Route,i,j)，Maze为迷宫，Route为走过的路径，i,j为当前节点。

按照我们的假定，右下角为出口，判断目标很简单：

    if i == Mazewidth-1 and j == Mazewidth-1:Route[i][j] = 1return

下一个节点的选择，按照右下左上，就是改变节点坐标为j+1,i+1,j-1,i-1。如探索右边的格子，可以这样做：

    if Route[i][j+1] == 0: #右边的格子空Route[i][j+1] = 1 #记录路径j = j+1move(Maze,Route,i,j) #递归

自然，我们还不要忘记不能撞墙，还不要越界。所以提供如下一个函数：

def issafe(Maze,i,j):if i >= 0 and i < Mazewidth and j >= 0 and j < Mazewidth  and Maze[i][j] == 0:return 1return 0

把这些组合起来，得到如下走迷宫的函数：

def move(Maze,Route,i,j):if i == Mazewidth-1 and j == Mazewidth-1:Route[i][j] = 1for row in Route: #打印路径print(' '.join([str(elem) for elem in row]))returnif issafe(Maze,i,j+1) == 1 and Route[i][j+1] == 0: #rightRoute[i][j+1] = 1j = j+1move(Maze,Route,i,j)else:if issafe(Maze,i+1,j) == 1 and Route[i+1][j] == 0: #downRoute[i+1][j] = 1i = i+1move(Maze,Route,i,j)else:if issafe(Maze,i,j-1) == 1 and Route[i][j-1] == 0: #leftRoute[i][j-1] = 1j = j-1move(Maze,Route,i,j)else:if issafe(Maze,i-1,j) == 1 and Route[i-1][j] == 0: #upRoute[i-1][j] = 1i = i-1move(Maze,Route,i,j)else:return

好，程序完成了，测试一下：

Mazewidth = 6Maze = [[0] * (Mazewidth) for i in range(Mazewidth)]Route = [[0] * (Mazewidth) for i in range(Mazewidth)]#Presetting the mazeMaze[1][0] = 1Maze[1][1] = 1Maze[1][2] = 1Maze[1][3] = 1Maze[1][4] = 1Maze[2][3] = 1Maze[2][4] = 1Maze[3][1] = 1Maze[4][1] = 1Maze[4][2] = 1Maze[4][3] = 1Maze[4][4] = 1Maze[4][5] = 1for row in Maze:print(' '.join([str(elem) for elem in row]))print('-----------')Route[0][0] = 1move(Maze,Route,0,0)

运行结果为：

0 0 0 0 0 01 1 1 1 1 00 0 0 1 1 00 1 0 0 0 00 1 1 1 1 10 0 0 0 0 0-----------1 1 1 1 1 10 0 0 0 0 11 1 1 0 0 11 0 1 1 1 11 0 0 0 0 01 1 1 1 1 1

上面是迷宫，下面是走过的路径。