请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。例如，在下面的3×4的矩阵中包含一条字符串“bfce”的路径（路径中的字母用加粗标出）。

[[“a”,”b”,”c”,”e”],
[“s”,”f”,”c”,”s”],
[“a”,”d”,”e”,”e”]]

但矩阵中不包含字符串“abfb”的路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入这个格子。

解题思路

使用深度遍历解题，一旦遇到解，直接退出，返回ture

代码

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        if not board:
            return False
        if not word:
            return False
        start = []
        self.h = len(board)
        self.w = len(board[0])
        mmapps = []
        for i in range(self.h):
            mapp=[]                 # 用于标记是否已经走过
            for j in range(self.w):                
                mapp.append(0)
                if word[0] == board[i][j]:
                    start.append((i,j, 0))
            mmapps.append(mapp)
        que = []
        for n in start:
            print(n)
            flag = self.dpth(mmapps, board, word, n)
            if flag == True:
                return True
        return False

    def dpth(self, mmapps, board, word, n):
        i,j, idx = n[0], n[1], n[2]
        mmapps[i][j] = -1
        if idx + 1< len(word):
            c = word[idx+1]
            if i+1 < self.h and c == board[i+1][j] and mmapps[i+1][j] == 0:
                flag = self.dpth(mmapps, board, word, (i+1, j, idx+1))
                if flag:
                    return flag
            if j+1 < self.w and c == board[i][j+1] and mmapps[i][j+1] == 0:
                flag = self.dpth(mmapps, board, word, (i, j+1, idx+1))
                if flag:
                    return True
            if i-1 >= 0 and c == board[i-1][j] and mmapps[i-1][j] == 0:
                flag = self.dpth(mmapps, board, word, (i-1, j, idx+1))
                if flag:
                    return True                
            if j-1 >= 0 and c == board[i][j-1] and mmapps[i][j-1] == 0:
                flag = self.dpth(mmapps, board, word, (i, j-1, idx+1))
                if flag:
                    return True                
        if idx+1 ==len(word):
            return True
        else:
            mmapps[i][j] = 0        # 退出这次深度，置0
            return False