矩阵中的路径

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

回溯法，终止条件：越界，不匹配，重复
1.先将matrix字符串映射为字符矩阵；
2.从原字符串中找到第一个跟str[0]相等的字符，得到其对应的在矩阵中的位置[r,c]
1）从[r,c]开始按 上、左、右、下的顺序搜索；
2）每当搜索到一个节点，先判断path是否包括它，包括就说明已经经过此节点，不能
再经过了；如果不包括，就将其加入path容器；
3）直到搜索到str[length - 1]节点，说明成功找到，标记result为true，标记
isFinished为true,尽快结束所有的递归操作；
4）如果某节点起的 上、左、右、下 都搜索过但还没找到结果，说明经过此节点的路
径都不满足题意，将其从path中删除，回溯到上一层继续找。
两种写法如下，思路相同，可以选择自己容易理解的写法。

def __init__(self):
    self._dict = {}
def hasPath(self, matrix, rows, cols, path):
    # write code here
    # 将矩阵转成二维数组表示
    x = [list(matrix[i*cols:(i+1)*cols]) for i in range(rows)]
    for i in range(rows):
        for j in range(cols):
            self._dict = {}
            if self.dfs(x, i, j, path):
                return True
    return False
'''
def dfs(self, matrix, i, j, p):#四个if语句中i,j边界判断保证了不越界，return保证了去掉不匹配的结果
    if matrix[i][j] == p[0]:
        if not p[1:]:#出口，路径中所有字母都找到
            return True
        matrix[i][j] = ''#先置为空，递归后再改回来，保证了不发生重复
        if i > 0 and self.dfs(matrix, i-1, j, p[1:]):#向上寻找，回溯体现在递归中
            return True
        if i < len(matrix)-1 and self.dfs(matrix, i+1, j ,p[1:]):#向下寻找
            return True
        if j > 0 and self.dfs(matrix, i, j-1, p[1:]):#向左寻找
            return True
        if j < len(matrix[0])-1 and self.dfs(matrix, i, j+1, p[1:]):#向右寻找
            return True
        matrix[i][j] = p[0]
        return False
    else:
        return False
'''
def dfs(self, matrix, i, j, p):

    if not (0 <= i< len(matrix) and 0 <= j < len(matrix[0])):  # 越界
        return False
    if matrix[i][j] != p[0]:  # 不匹配
        return False
    if self._dict.get((i,j)) is not None:  # 重复路径
        return False
    self._dict[(i,j)] = 1
    if not p[1:]:
        return True
    # 向上下左右寻找
    return self.dfs(matrix,i+1,j,p[1:]) or self.dfs(matrix,i-1,j,p[1:]) or self.dfs(matrix,i,j+1,p[1:]) or self.dfs(matrix,i,j-1,p[1:])