2019-08-21剑指 矩阵中的路径

50min
1.行和列写反了
2.没有递归停止条件了
3.return只返回第一个的错误
还好k和visited都记得还原了

class Solution:
    def hasPath(self, matrix, rows, cols, path):
        if not matrix or not path or rows<=0 or cols<=0:return False
        visited=[False for i in range(len(matrix))]
        for index,c in enumerate(matrix):
            if c==path[0]:
                i, j = index // cols, index % cols
                # print(i,j,c)
                if self.dfs(matrix,rows,cols,path,visited,i,j,0):return True #不能只返回第一个
        return False

    def dfs(self,matrix,rows,cols,path,visited,i,j,k):
        if self.check_valid(matrix,rows,cols,path,visited,i,j,k):
            if k==len(path)-1:return True # 递归终止条件忘了
            visited[i*cols+j]=True
            t1=self.dfs(matrix,rows,cols,path,visited,i+1,j,k+1) # 这里k不用单独+-
            t2=self.dfs(matrix,rows,cols,path,visited,i-1,j,k+1) # 这里k不用单独+-
            t3=self.dfs(matrix,rows,cols,path,visited,i,j+1,k+1) # 这里k不用单独+-
            t4=self.dfs(matrix,rows,cols,path,visited,i,j-1,k+1) # 这里k不用单独+-
            visited[i*cols+j]=False
            return t1 or t2 or t3 or t4
        return False



    def check_valid(self,matrix,rows,cols,path,visited,i,j,k):
        if i<0 or i>=rows or j<0 or j>=cols:return False #行和列写反了
        index=i*cols+j
        if visited[index] or matrix[index] != path[k]:return False
        return True