剑指offer 矩阵中的路径

思想：标准的回溯法
实现：

• 使用hash表标记元素是否已经被访问
• 使用全局变量以及在函数内定义函数尽量减少代码量

class Solution_hash:
    def hasPath(self, matrix, rows, cols, path):
        if not matrix or cols < 1 or rows < 1 or not path:
            return False

        self.hash = {}

        def DFS(i, j, index):
            if check(i, j, index):
                self.hash[(i, j)] = 1  # 标记当前节点已经被访问
                if index == len(path) - 1: return True
                flag = DFS(i + 1, j, index + 1) or DFS(i, j + 1, index + 1) or \
                       DFS(i - 1, j, index + 1) or DFS(i, j - 1, index + 1)
                self.hash.pop((i, j))  # 当前节点的后续节点都没有找到合适的路径 释放点当前节点 允许再次访问
                return flag
            return False

        def check(i, j, index):  # 对于当前节点的合法性进行判断
            return 0 <= i < rows and 0 <= j < cols and (i, j) not in self.hash and matrix[i * cols + j] == path[index]

        for i in range(rows):
            for j in range(cols):
                if DFS(i, j, 0): return True
        return False