23. 矩阵中的路径

题目描述

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。
路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。
如果一条路径经过了矩阵中的某一个格子，则之后不能再次进入这个格子。

注意：

• 输入的路径不为空；
• 所有出现的字符均为大写英文字母；

样例

matrix=
[
  ["A","B","C","E"],
  ["S","F","C","S"],
  ["A","D","E","E"]
]

str="BCCE" , return "true" 

str="ASAE" , return "false"

Code

DFS

1. 注意DFS的模板写法
2. 特别注意，是否需要还原现场

class Solution(object):
    def dfs(self,x,y,u):
        # u表示当前寻找的字符串的位数
        if self.matrix[x][y] != self.string[u]:
            return False
        if u == self.length - 1:
            return True
        self.state[x][y] = 1

        for i in range(4):
            a = x + self.dx[i]
            b = y + self.dy[i]
            if 0<=a<self.n and 0<=b<self.m and not self.state[a][b]:
                if self.dfs(a,b,u+1):
                    return True
                # 还原现场
                self.state[a][b] = 0


    def hasPath(self, matrix, string):
        """
        :type matrix: List[List[str]]
        :type string: str
        :rtype: bool
        """
        self.matrix = matrix
        self.string = string
        self.length = len(string)
        self.n = len(matrix)
        if self.n == 0:
            return False
        self.m = len(matrix[0])
        self.dx = [-1,0,1,0]
        self.dy = [0,1,0,-1]

        for i in range(self.n):
            for j in range(self.m):
                if matrix[i][j] == string[0]:
                    self.state = [[0] * self.m for _ in range(self.n)]
                    if self.dfs(i,j,0):
                        return True

        return False