题解 | #矩阵中的路径#

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

    def hasPath(self , matrix: List[List[str]], word: str) -> bool:
        # write code here
        self.dx = [-1, 0, 1, 0]
        self.dy = [0, 1, 0, -1]
        self.matrix = matrix
        self.word = word
        self.n = len(matrix)
        self.m = len(matrix[0])
        self.st = [[False] * self.m for _ in range(self.n)]
        # 找到爆搜起点
        for i in range(self.n):
            for j in range(self.m):
                if matrix[i][j] == word[0] and self.dfs(i, j, 0):
                    return True
        
        return False
    
    def dfs(self, x, y, u):
        # 表matrix[x][y]是否与word[u]匹配
        if self.matrix[x][y] != self.word[u]: return False # 匹配
        else:
            if u == len(self.word) - 1: return True # 匹配完毕
            self.st[x][y] = True # 路过标记
            for i in range(4): # 向四周找寻下一个匹配
                a = x + self.dx[i]
                b = y + self.dy[i]
                if a >= 0 and a < self.n and b >= 0 and b < self.m:
                    if not self.st[a][b] and self.dfs(a, b, u+1):
                        return True
            self.st[x][y] = False # 恢复现场
        # 匹配不上
        return False