题解 | #矩阵中的路径#

# 我对这题的想法是，将之前走过的路径用元组列表的方式进行存储
class Solution:
    res = False

    def hasPath(self, matrix: List[List[str]], word: str) -> bool:
        # write code here
        self.res = False
        self.myBacktracking(matrix, [], word)
        return self.res

    def myBacktracking(self, matrix: List[List[str]], path: List, word: str):
        # 1.回溯的终止条件，因为我加入了剪枝，因此只需要长度相符就可以
        if self.res == True:
            return
        if path and len(path) == len(word):
            temp = path[-1]
            if word[-1] == matrix[temp[0]][temp[1]]:
                self.res = True
                return
        # 2.1回溯的分支选择，初始为，起点任意，也要回溯
        if len(path) == 0:
            # path = []
            for i in range(len(matrix)):
                for j in range(len(matrix[0])):
                    path.append((i, j))
                    self.myBacktracking(matrix, path, word)
                    path.pop()
        else:
            # 3.剪枝，当前路径字符串已经不对，不需要往下走了
            # 检查当前路径
            for ind, val in enumerate(path):
                pathchar = matrix[val[0]][val[1]]
                if pathchar != word[ind]:
                    return
            # 2.2分支选择path的最后一个元素代表上次走到哪里了，朝他的四周考虑
            # 但如果四周某个元素已经在路径中则放弃选择
            # 4.回溯，每个选择要撤回，再去做别的选择
            i, j = path[-1]
            # 上，右，下，左
            if i - 1 >= 0 and (i - 1, j) not in path:
                path.append((i - 1, j))
                self.myBacktracking(matrix, path, word)
                path.pop()
            if j + 1 < len(matrix[0]) and (i, j + 1) not in path:
                path.append((i, j + 1))
                self.myBacktracking(matrix, path, word)
                path.pop()
            if i + 1 < len(matrix) and (i + 1, j) not in path:
                path.append((i + 1, j))
                self.myBacktracking(matrix, path, word)
                path.pop()
            if j - 1 >= 0 and (i, j - 1) not in path:
                path.append((i, j - 1))
                self.myBacktracking(matrix, path, word)
                path.pop()