【剑指offer】矩阵中的路径（python）

1. str转换为list

在将str转化为list时，主要就是通过str的split()函数，split()参数为空时，默认以空格来做分割。

直接通过list转换时是以每一个字符为分割的。

2. python申明多维数组

list_three = [[0 for i in range(3)] for j in range(3)]
注意方括号

3. 回溯法

一种暴力搜索方法，在一次搜索结束时需要进行回退，将这一次搜索过程中设置的状态清楚，再开始一次新的搜索过程。 
mark[r][c] = True
for i in self.next:
    if self.backTrack(matrix, pathList, mark, pathLen+1, r+i[0], c+i[1]):
       return True
mark[r][c] = False
这里就表示，从[r][c]开始，设置为True，下一步搜索四个方向，下一次搜索结束后，将[r][c]状态清除。
这里next = [[0,-1],[0,1],[-1,0],[1,0]]，标记了下次搜索的可能方向。 
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param matrix string字符串 
# @param rows int整型 
# @param cols int整型 
# @param str string字符串 
# @return bool布尔型
#
class Solution:
    next = [[1,0],[-1,0],[0,1],[0,-1]]
    def hasPath(self , matrix , rows , cols , str ):
        # write code here
        if (rows == 0) or (cols == 0): return False
        matrix = self.buildMatrix(matrix, rows, cols)
        targetPath = list(str)
        mark = [[False for i in range(cols)] for j in range(rows)]
        for i in range(rows):
            for j in range(cols):
                if self.backTravesal(matrix, mark, targetPath, 0, i, j):
                    return True
        return False
    def backTravesal(self, matrix, mark,targetPath, targetPathIndex, r, c):
        if targetPathIndex == len(targetPath): return True
        rows = len(matrix)
        cols = len(matrix[0])
        if (r < 0) or (r >= rows) or (c < 0) or (c >= cols) or mark[r][c] or (matrix[r][c]!= targetPath[targetPathIndex]):
            return False
        mark[r][c] = True
        for i in self.next:
            if self.backTravesal(matrix, mark, targetPath, targetPathIndex+1, r+i[0], c+i[1]):
                return True
        mark[r][c] = False
        return False
    def buildMatrix(self, string, rows, cols):
        matrix = [[-1 for i in range(cols)] for j in range(rows)]
        stringList = list(string)
        index = 0
        for i in range(rows):
            for j in range(cols):
                matrix[i][j] = stringList[index]
                index += 1
        return matrix