12. 矩阵中的路径

• 利用回溯的方法

1. 设置visited矩阵，当走过i，j点时，将此点设置为1，因为不能重复进入一个格子
2. 如果第ij个点与path中的字符一样且未走过，则暂时进入这个格子
3. 向四周搜寻下一步的走法，若无解，则证明上一个path路径不对，退回到前一个字符
4. 若正确，则重复上述过程，返回haspath

class Solution:
    def hasPath(self, matrix, rows, cols, path):
        # write code here
        if not matrix or not path:
            return False
        visited = [0]*cols*rows
        pathLenth = 0
        for i in range(rows):
            for j in range(cols):
                if self.hasPathCore(matrix, i, j, rows, cols, path, pathLenth, visited):
                    return True
        return False
    def hasPathCore(self, matrix, i, j, rows, cols, path, pathLenth, visited):
        if pathLenth == len(path):
            return True
        hasPath = False
        if 0 <= i < rows and 0 <= j < cols and matrix[i*cols+j] == path[pathLenth] and not visited[i*cols+j]:
            pathLenth += 1
            visited[i*cols+j] = 1
            hasPath = self.hasPathCore(matrix, i, j-1, rows, cols, path, pathLenth, visited) or \
            self.hasPathCore(matrix, i-1, j, rows, cols, path, pathLenth, visited) or\
            self.hasPathCore(matrix, i, j+1, rows, cols, path, pathLenth, visited) or\
            self.hasPathCore(matrix, i+1, j, rows, cols, path, pathLenth, visited)
            if not hasPath:
                pathLenth -= 1
                visited[i*cols+j] = 0
        return hasPath