题解 | #矩阵中的路径#

递归回溯思想进行解题，这题很难搞，我不会，在学习，注意想法和细节实现

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param matrix char字符型二维数组 
# @param word string字符串 
# @return bool布尔型
# 递归算法进行求解，将原问题转化为，一个较小规模的问题进行求解
# 使用回溯算法进行求解，回溯遍历算法
class Solution:
    def hasPath(self , matrix: List[List[str]], word: str) -> bool:
        # write code here
        # 使用递归的思想进行求解
        # 优先处理，矩阵为空的情况
        if len(matrix)==0:
            return False
        
        # 设置相应的数组，记录某一次遍历时，矩阵位置元素是否被走过
        n = len(matrix)
        m = len(matrix[0])
        flag = [[0 for i in range(m)] for j in range(n)]  # 
        # 定义一个长度跟输入列表纬度相同的下标标识
        
    
        
        
        # 递归查找，到了矩阵的边界或者是不匹配，或者是已经走过，或者检索完成都结束递归调用
        # 访问节点的时候，改flag元素，向其他四个方向走，回溯修改flag数组
        
        # 一个一个的去寻找相应的字符
        for i in range(n):
            for j in range(m):
                # 如果能够遍历通过
                if self.dfs(matrix, n, m, i, j, word, 0, flag):
                    return True
        return False
    def dfs(self, matrix, n, m, i, j, word, k, flag):
        """
        matrix, 传入的矩阵
        n, 矩阵的第一个维度
        m, 矩阵的第二个维度
        i,  j,矩阵搜索位置
        word, 搜索的数字
        k, 记录第几个字符
        flag，标记矩阵，用于记录是否到过
        """
        if i<0 or i>=n or j<0 or j>=m  or (matrix[i][j]!=word[k]) or flag[i][j]:
            return False # 排除其他的情况
        # 使用k记录当前为第几个字符
        if k == len(word) -1:
            return True
        flag[i][j] = 1  # 表示遍历过了
        # 如果当前节点的任意方向都可行的话
        if ((self.dfs(matrix, n, m, i-1, j, word, k+1, flag)) or
            (self.dfs(matrix, n, m, i, j-1, word, k+1, flag)) or
            (self.dfs(matrix, n, m, i+1, j, word, k+1, flag)) or 
            (self.dfs(matrix, n, m, i, j+1, word, k+1, flag))
           ):
            return True
        # 没有路径，被占用
        flag[i][j] = 0
        return False