矩阵中的路径

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param matrix char字符型二维数组 
# @param word string字符串 
# @return bool布尔型
#
class Solution:
    def dfs(self,m,path,i,j):
        if not path:
            return True
        if i>-1 and j>-1 and i<len(m) and j<len(m[0]) and m[i][j]==path[0]:
            tmp =m[i][j]
            m[i][j] = None
            ret = self.dfs(m,path[1:],i-1,j)&nbs***bsp;self.dfs(m,path[1:],i+1,j)&nbs***bsp;self.dfs(m,path[1:],i,j-1)&nbs***bsp;self.dfs(m,path[1:],i,j+1)
            m[i][j] = tmp
            return ret
        else:
            return False
    def hasPath(self , matrix: List[List[str]], word: str) -> bool:
        # write code here
        if not matrix:
            return False
        if not word:
            return True
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if self.dfs(matrix, word, i, j):
                    return True
        return False

class Solution:
    def hasPath(self , matrix , word ):
        for x in matrix:        # 在 matrix 四周包上一层 0, 省的后面要判断越界
            x.append(0)
            x.insert(0,0)
        matrix.append([0]*len(matrix[0]))
        matrix.insert(0,[0]*len(matrix[0]))

        def findpath(location, word, res):    # location: 第一个字符在matrix中的位置; word: 下一步需要的字符串; res: 已经走过的格子
            if word == "":                  # 每匹配到一个字符就后移一位: "abcced" - "bcced" - ... ""
                return True
            i, j = location
            for x in [[i + 1, j], [i - 1, j], [i, j + 1], [i, j - 1]]:  # 依次检查 location 上下左右的四个位置
                if matrix[x[0]][x[1]] == word[0] and x not in res:      # 如果其等于当前的头字符并且没有访问过
                    res.append(x)
                    temp = word[0]         # temp用于回溯, 重构上一级的字符串
                    word = word[1:]        # 字符串后移, 匹配下一个
                    if findpath(x, word, res) == True:  # 如果最终匹配完, word = "", 会返回 true
                        return True
                    else:                  # 如果未返回 true, 那这条路径失败, 回溯
                        res.pop()          # 将其从以访问的去掉
                        word = temp + word # 重构 word

        start = word[0]
        word = word[1:]     # 因为在寻找头节点的过程中, 第一个字符已匹配, 所以从第二个开始
        for i in range(1, len(matrix)-1):
            for j in range(1, len(matrix[0])-1):
                if matrix[i][j] == start:   # 找到头节点, 开始递归
                    res = [[i,j]]
                    if findpath([i,j], word, res):
                        return True
        return False

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param matrix char字符型二维数组 
# @param word string字符串 
# @return bool布尔型
#
class Solution:
    def hasPath(self , matrix , word ):
        # write code here
        ##布尔矩阵
        visited=[[False for i in range(len(matrix[0]))]for j in range(len(matrix))]
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if self.dfs(matrix,word,visited,i,j):
                    return True
        return False
       
    def dfs(self,matrix,word,visited,x,y):
        if not word:
            return True
        if not visited[x][y]:
            if matrix[x][y]==word[0]:
                if len(word)==1:
                    return True
                visited[x][y]=True
                ##down
                if x+1<len(matrix) and self.dfs(matrix,word[1:],visited,x+1,y):
                    return True
                ##up
                if x-1>=0 and self.dfs(matrix,word[1:],visited,x-1,y):
                    return True
                ##right
                if y+1<len(matrix[0]) and self.dfs(matrix,word[1:],visited,x,y+1):
                    return True
                ##left
                if y-1>=0 and self.dfs(matrix,word[1:],visited,x,y-1):
                    return True
                ##都不成立 返回上一节点 (x,y)位置变为没访问过的状态
                visited[x][y]=False
        return False

class Solution:
    def hasPath(self, matrix, word):
        # write code here
        visited_row = []  # matrix形状的每一行
        visited = []    # matrix形状的bool矩阵，False代表每个格子都没有路过
        for jj in range(len(matrix[0])):
            visited_row.append(False)
        for ii in range(len(matrix)):
            visited.append(visited_row[:])  # 每行复制的时候一定要加[:]!!!要不就变成复制地址了！！！


        for i in range(len(matrix)):
            for j in range(len(matrix[0])):    # j,搜寻路径起点的纵坐标
                if self.DFS(matrix, word, visited, i, j):
                    return True
        return False


    def DFS(self, matrix, word, visited, x, y):
        if not word:
            return True
        if not visited[x][y]:
            if matrix[x][y] == word[0]:
                if len(word[1:]) == 0:
                    return True
                visited[x][y] = True   # 如果上面三条通过，则说明该点是合理的，接下来考察该点，修改标记
                if x+1<len(matrix) and self.DFS(matrix, word[1:], visited, x+1, y):  # 从四个方向开始寻找
                    return True
                if x-1>=0 and self.DFS(matrix, word[1:], visited, x-1, y):
                    return True
                if y+1<len(matrix[0]) and self.DFS(matrix, word[1:], visited, x, y+1):
                    return True
                if y-1>=0 and self.DFS(matrix, word[1:], visited, x, y-1):
                    return True
                visited[x][y] = False   # 如果四个方向都不对，那么说明该点不是正确的。
        return False