题解 | #矩阵中的路径#

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param matrix char字符型二维数组
# @param word string字符串
# @return bool布尔型
#
class Solution:
 


    def hasPath(self, matrix: list[list[str]], word: str) -> bool:
        # write code here
        n = len(matrix)  # 计算矩阵的行
        m = len(matrix[0])  # 计算矩阵的列

        if n==0 or m==0:
            return False
        #初始化标记数组，用来记录哪些点被访问过哪些没有
        flag = [[False for i in range(m)] for i in range(n)]
        index = 0
        res=False
		#定义深度搜索函数，进行递归搜索，如果满足条件，就调用递归函数进行下一层的搜索，记得进入递归之前标记一下，返回后再标记回来，别影响下一个方向的递归。递归终止的条件是index的值等于word的长度
        def dfs(i, j, matrix,word, index,res):
            dxy = [[1, 0], [-1, 0], [0, 1], [0, -1]]
            if index == len(word):
                return True
            else:
                for k in range(4):
                    i = i + dxy[k][0]
                    j = j + dxy[k][1]
                    if 0 <= i < n and 0 <= j < m and( not flag[i][j]):
                        if matrix[i][j] == word[index]:
                            flag[i][j] = True
                            if dfs(i, j, matrix, word,index + 1,res):
                                return True
                            flag[i][j] = False
                    
                    i=i- dxy[k][0]
                    j=j- dxy[k][1]
                return False
        
        
        for i in range(n):
            for j in range(m):
                if matrix[i][j] == word[index]:
                    flag[i][j] = True
                    if dfs(i, j, matrix,word, index+1,res):
                        return True
                    flag[i][j] = False
        return False