【正确答案】最容易想到的方法就是尝试所有可能的路径，找出可达的一条路。显然这种方法效率非常低下，这里重点介绍一种效率更高的回溯法。主要思路为：当碰到死胡同的时候，回溯到前一步，然后从前一步出发继续寻找可达的路径。算法的主要框架为：

申请一个结果矩阵来标记移动的路径 　　if　到达了目的地 　　打印解决方案矩阵 　　else 　　(1)在结果矩阵中标记当前为1(1表示移动的路径)。 　　(2)向右前进一步，然后递归地检查，走完这一步后，判断是否存在到终点的可达的 路线。 　　(3)如果步骤(2)中的移动方法导致没有通往终点的路径，那么选择向下移动一步， 然后检查使用这种移动方法后，是否存在到终点的可达的路线。 　　(4)如果上面的移动方法都会导致没有可达的路径，那么标记当前单元格在结果矩阵 中为0，返回false，并回溯到前一步中。

   根据以上框架很容易进行代码实现。示例代码如下：
   class Maze:
   def __init__(self):
   self.N=4
   #打印从起点到终点的路线
   def printSolution(self,sol):
   i=0
   while i＜self.N:
   j=0
   while j＜self.N:
   print sol[i][j],
   j+=1
   print '\n'
   i+=1
   #判断x和y是否是一个合理的单元
   def isSafe(self,maze,x,y):
   return x＞=0 and x＜self.N and y＞=0 and\
   y＜self.N and maze[x][y]==1
   """
   使用回溯的方法找到一条从左上角到右下角的路径
   maze表示迷宫,x、y表示起点,sol存储结果
   """
   def getPath(self,maze,x,y,sol):
   #到达目的地
   if x==self.N-1 and y==self.N-1:
   sol[x][y]=1
   return True
   #判断maze[x][y]是否是一个可走的单元
   if self.isSafe(maze,x,y):
   #标记当前单元为1
   sol[x][y]=1
   #向右走一步
   if self.getPath(maze,x+1,y,sol):
   return True
   #向下走一步
   if self.getPath(maze,x,y+1,sol):
   return True
   #标记当前单元为0用来表示这条路不可行,然后回溯
   sol[x][y]=0
   return False
   return False
   
   if __name__=="__main__":
   rat=Maze()
   maze=[[1,0,0,0],
   [1,1,0,1],
   [0,1,0,0],
   [1,1,1,1]]
   sol=[[0,0,0,0],
   [0,0,0,0],
   [0,0,0,0],
   [0,0,0,0]]
   if not rat.getPath(maze,0,0,sol):
   print "不存在可达的路径"
   else:
   rat.printSolution(sol)
   程序的运行结果为：
   1 0 0 0
   1 1 0 0
   0 1 0 0
   0 1 1 1

【答案解析】[考点] 如何求解迷宫问题