回溯

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param matrix char字符型二维数组 
# @param word string字符串 
# @return bool布尔型
#
class Solution:
    def hasPath(self , matrix: List[List[str]], word: str) -> bool:
    	#如果矩阵为空或字符串为空，不满足条件
        if matrix == [[]] or word == '':
            return False
        rows = len(matrix)
        cols = len(matrix[0])
        # 设置和matrix大小相同的visited矩阵，保存每个元素是否被访问过
        visited = [[0] * cols for _ in range(rows)]
        pathlength = 0
        
        def backtracking(matrix,word,col,row,pathlength):
            haspath = False
            #如果遍历路径长度等于字符串长度，那么已经找到了这条路径
            if pathlength >= len(word):
                return True
            #行列都要在矩阵范围里，并且该元素与字符串当前访问值相同且没被访问过
            if 0<=row<rows and 0<=col<cols and matrix[row][col] == word[pathlength] and visited[row][col] == 0:
            	#遍历长度加一，标记已经被访问
                pathlength += 1
                visited[row][col] = 1
                #上下左右四个方向，开始下一步的搜索
                haspath = backtracking(matrix, word, col-1, row, pathlength) or backtracking(matrix, word, col, row-1, pathlength) or backtracking(matrix, word, col+1, row, pathlength) or backtracking(matrix, word, col, row+1, pathlength)
                #如果上下左右都没有搜索到，需要回溯到上一步
                if haspath == False:
                    pathlength -= 1
                    visited[row][col] = 0
            return haspath
        #矩阵中的每个位置都当作起始节点，开始查找搜索路径
        for i in range(rows):
            for j in range(cols):
                if backtracking(matrix, word, j, i, pathlength):
                    return True
        return False