题解 | #矩阵中的路径#

#
class Solution:
    def hasPath(self , matrix: List[List[str]], word: str) -> bool:
        a = []
        col = len(matrix)
        row = len(matrix[0])
        # 深度优先搜索 + 回溯。i,j描述矩阵的位置，k描述要匹配的字符的位置
        # 设置一个列表记录已访问位置(i, j)，如False就回溯，即出栈
        def dfs(i,j,k):
            # 出界，已访问，不等。都返回False
            if i not in range(col) or j not in range(row) or (i, j) in a or matrix[i][j] != word[k]:
                return False
            # 如果匹配成功并到了最后，返回True
            if k == len(word) - 1:
                return True
            # 未到最后，当前匹配成功，先将位置入栈
            a.append((i, j))
            # 递归搜索后续的，返回False之前要先出栈
            if not (dfs(i + 1, j, k + 1) or dfs(i - 1, j, k + 1) or dfs(i, j + 1, k + 1) or dfs(i, j - 1, k + 1)):    
                a.pop()
                return False
            else:
                # a.pop()
                return True
        # 主程序：循环矩阵搜索和第一个即word[0]匹配的，并进入dfs深度搜索函数。
        for i in range(col):
            for j in range(row):
                if matrix[i][j] == word[0]:
                    if dfs(i,j,0):
                        return True
        return False