题解 | #矩阵中的路径#

思路：dfs遍历，i，j控制matrix遍历坐标，idx控制word遍历坐标，idx到达word末尾，成功，越界或matrix上字符与word当前判断字符不同，失败

注意：

1、idx的增加，无论是在当前过程，还是递归中，均要在判断idx遍历结束和字符不匹配之后进行

2、为了防止遍历过程中回头，需要遮挡，并在递归结束后恢复

3、多word与matrix当前字符相同，idx到达n-1，成功

class Solution:
    def hasPath(self , matrix: List[List[str]], word: str) -> bool:
        # write code here
        if len(matrix) == 0 or len(matrix[0]) == 0:
            return False
        
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j] == word[0] and self.dfs(matrix, i, j, word, 0):
                    return True
        return False

    def dfs(self, matrix, i, j, word, idx):
        if i < 0 or i >= len(matrix) or j < 0 or j >= len(matrix[0]):
            return False
        
        if matrix[i][j] != word[idx]:
            return False
        
        if idx == len(word)-1:
            return True
        
        tmp = matrix[i][j]
        matrix[i][j] = '#'
        
        if self.dfs(matrix, i+1, j, word, idx+1) or \
        self.dfs(matrix, i-1, j, word, idx+1) or \
        self.dfs(matrix, i, j+1, word, idx+1) or \
        self.dfs(matrix, i, j-1, word, idx+1):
            return True
        matrix[i][j] = tmp
        
        return False