【剑指Offer】65矩阵中的路径

た入场券 2022-04-11 11:56 107阅读 0赞

## 题目描述 ##

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则之后不能再次进入这个格子。 例如 a b c e s f c s a d e e 这样的3 X 4 矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。

时间限制：1秒；空间限制：32768K

## 解题思路 ##

本题用到回溯法求解，用递归实现回溯。回溯法（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

class Solution:
        def hasPath(self, matrix, rows, cols, path):
            for i in range(rows):
                for j in range(cols):
                    if matrix[i*cols+j]==path[0] and self.find(list(matrix),rows,cols,path[1:],i,j):
                        return True
            return False
        # 递归查找位置ij附近有没有元素path[0]
        def find(self,matrix,rows,cols,path,i,j):
            if not path: #注意这种写法 写成if path==[]/if path==None都不对
                return True
            mat = matrix
            mat[i*cols+j]='0' #标记为'0'，表示之后递归中该格子不能再次进入
            if j+1<cols and mat[i*cols+(j+1)]==path[0]:
                return self.find(list(mat),rows,cols,path[1:],i,j+1)
            elif j-1>=0 and mat[i*cols+(j-1)]==path[0]:
                return self.find(list(mat),rows,cols,path[1:],i,j-1)
            elif i+1<rows and mat[(i+1)*cols+j]==path[0]:
                return self.find(list(mat),rows,cols,path[1:],i+1,j)
            elif i-1>=0 and mat[(i-1)*cols+j]==path[0]:
                return self.find(list(mat),rows,cols,path[1:],i-1,j)
            else:
                return False