题解 | #矩阵中的路径#

#与题目【腐烂的橘子】类似，但本题使用的是DFS，应该后进先出，同时有了不能走回头路的限制
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param matrix char字符型二维数组 
# @param word string字符串 
# @return bool布尔型
#
class Solution:
    def hasPath(self , matrix: List[List[str]], word: str) -> bool:
        # write code here
        M,N=len(matrix),len(matrix[0])
        def neighb(a,b):
            for (i,j) in ((a+1,b),(a-1,b),(a,b+1),(a,b-1)):
                if 0<=i<M and 0<=j<N:
                    yield i,j
        f=word[0]
        res=[]
        visits=[]
        for i,l in enumerate(matrix):
            for j,v in enumerate(l):
                if v==f:
                    res.append((i,j,0))
        prev=-1
        while res:
            i,j,idx=res.pop(0)
            if idx==prev:
                visits.clear()
            prev=idx
            visits.append((i,j))
            if idx==len(word)-1:
                return True
            for x,y in neighb(i,j):
                if matrix[x][y]==word[idx+1] and (x,y) not in visits:
                    res.insert(0,(x,y,idx+1))
        print(visits)
        return False