题解 | #矩阵中的路径#

DFS最优遍历，首先很简单能想到 上下左右 分别对应 (x,y) 的加减， 

所以代码的大致轮廓我们应该能写出来，就是遍历矩形所有的点，然后从这个点开始往他的4个方向走，因为是二维数组，所以有两个for循环，代码如下 hasPath,

关键代码是DFS这个函数，用到了递归，要注意递归要有终止条件，而且要注意[1:]和[1]的区别

class Solution:
    def hasPath(self , matrix , word ):
        # write code here
        visited = [[0 for i in range(len(matrix[0]))] for j in range(len(matrix))]#建立一个用来mark不会重复走同一个格子的matrix，默认置0，走过一次则置为1
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if self.DFS(i, j, matrix, visited, word):#
                    return True
        return False
     
    def DFS(self, x, y, matrix, visited, word):
        if not visited[x][y]:
            if matrix[x][y] == word[0]:
                visited[x][y] = 1#visited默认置0，走过一次则置为1
                if len(word[1:]) == 0:#中止条件,注意此处既判断了word[1]有没有值，也不会报错，如果直接用len(word[1]）== 0则不行，因为word里只有一个值时，word[1]可以调用但是word[1:]不可以
                    return True
                if y+1 <= len(matrix[0])-1 and self.DFS(x,y+1, matrix, visited, word[1:]):#如果满足则走下一步y+1
                    return True
                if x+1 <= len(matrix)-1 and self.DFS(x+1, y, matrix, visited, word[1:]):#如果y+1不满足，则走下一步x+1
                    return True
                if x-1 >= 0 and self.DFS(x-1, y, matrix, visited, word[1:]):#如果x+1.y+1都不满足，则走x-1
                    return True
                if y-1 >= 0 and self.DFS(x, y-1, matrix, visited, word[1:]):#如果x+1,y+1,x-1都不满足，则走y-1
                    return True
                visited[x][y] = 0#如果上下左右都不满足，则将已经走过的(x,y)全部置0，为下一次新的
        return False