题解 | #矩阵中的路径#

本题主要是利用 dfs 进行求解，给出的条件是任意起点，则 matrix 中等于 word[0] 的均可作为路径的起点，同时每次访问需要记录已经过的节点,需要注意的是上一次的已访问节点不会影响下一次的访问,所以在本次访问中,若没有找到完整路径需将已访问节点恢复初始状态;
代码如下:

def hasPath(self , matrix , word ):
        # write code here
        def dfs(visited, x, y, s):
            if s == len(word):
                return True
            if x < 0 or x >= m or y < 0 or y >= n or visited[x][y] or matrix[x][y] != word[s]:
                return False
            visited[x][y] = True
            for di, dj in dirs:
                xi, yj = x + di, y + dj
                if dfs(visited, xi, yj, s + 1):
                    return True
            visited[x][y] = False


        m, n = len(matrix), len(matrix[0])
        visited = [[False for _ in range(n)] for _ in range(m)]
        dirs = [(-1, 0), (0, 1), (1, 0), (0, -1)]
        for i in range(m):
            for j in range(n):
                if matrix[i][j] == word[0]:
                    if dfs(visited, i, j, 0):
                        return True
        return False