题解 | #矩阵中的路径#

class Solution:
    def hasPath(self , matrix: List[List[str]], word: str) -> bool:
        # write code here
        row = len(matrix)
        col = len(matrix[0])
        
        def dfs(i, j, k, visited):           #visisted已访问的坐标set()，当前符合长度
            if k == len(word):
                return True
            for x, y in [(1,0), (-1,0), (0,1), (0,-1)]:
                tmp_i = i + x
                tmp_j = j + y
                if 0<=tmp_i<row and 0<=tmp_j<col and (tmp_i,tmp_j) not in visited and matrix[tmp_i][tmp_j] == word[k]:
                    visited.add((tmp_i,tmp_j))
                    if dfs(tmp_i, tmp_j, k+1, visited):
                        return True                 #开始递归，如果最后k==len(word)则输出True，如果不行则回溯
                    visited.remove((tmp_i,tmp_j))
            return False
            
        for i in range(row):
            for j in range(col):
                if matrix[i][j] == word[0] and dfs(i, j, 1,{(i, j)}):   #找起点
                        return True
        return False