面试题66: 矩阵中的路径

题目：
https://www.nowcoder.com/practice/c61c6999eecb4b8f88a98f66b273a3cc?tpId=13&tqId=11218&tPage=4&rp=3&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking

Code

# -*- coding:utf-8 -*-
class Solution:
    "matirx ,rows , cols , path "
    def hasPath(self, matrix, rows, cols, path):
        visit = []
        for i in range(rows):
            row = []
            for j in range(cols):
                row.append(False)
            visit.append(row)
        for i in range(rows):
            for j in range(cols):
                if self.findPath(matrix,rows,cols,i,j,path,0,visit):
                        return True
        return False
        
    def findPath(self,matrix,rows,cols,row,col,path,pathlen,visit):
        if pathlen==len(path):
            return True
        haspath = False

        if row>=0 and row< rows and col >= 0 and col < cols and matrix[row*cols+col]==path[pathlen] and not visit[row][col]:
            visit[row][col] = True
            pathlen = pathlen + 1
            haspath = self.findPath(matrix,rows,cols,row-1,col,path,pathlen,visit) or \
            self.findPath(matrix,rows,cols,row+1,col,path,pathlen,visit) or \
            self.findPath(matrix,rows,cols,row,col+1,path,pathlen,visit) or \
            self.findPath(matrix,rows,cols,row,col-1,path,pathlen,visit)
        
            if not haspath:  #这个部分很重要，如果发现，递归不能找到，则回退，路径长度减1，并且把访问矩阵置为Flase
                pathlen = pathlen - 1
                visit[row][col] = False
        return haspath

心得：
1、用python编代码，要注意输入和输出，尤其是参数输入
2、关于回溯问题，这个题很经典。与面试题67不同的是，面试67题，访问矩阵只要访问过了就是访问过了，因为是要求可以到达那些地方，只要是到达了就可以。
但是，本题，是求路径是否符合。在下一层递归退出以后，如果没有找到的话，需要将路径再减1，然后访问矩阵置为False。
3、就是递归代码的设计，这个递归是返回True或False，这个是只要有一个递归能找到就可以，则用或运算。
4、对于递归算法，推出条件是很关键。