题目：
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。
路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。
如果一条路径经过了矩阵中的某一个格子，则之后不能再次进入这个格子。
例如 a b c e s f c s a d e e 这样的3 X 4 矩阵中 包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，
因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。
思路：
回溯法：找不到下一个目标时，就回退到上一个找到了的目标。
1）先遍历这个矩阵，找到路径中的第一个字符a
2）然后遍历第一个字符a上下左右的字符，找有无路径中的第二个字符。
如果有和字符串str中下一个字符相同的，就把那个字符当作下一个字符（下一次遍历的起点）
如果没有，就需要回退到上一个字符，然后重新遍历。
为了避免路径重叠，需要一个辅助矩阵【boolmatrix】来记录路径情况。
下面代码中，当矩阵坐标为（row，col）的格子和路径字符串中下标为pathLength的字符一样时，从4个相邻的格子（row，col-1）、（row-1，col）、（row，col+1）以及（row+1，col）中去定位路径字符串中下标为pathLength+1的字符。
如果4个相邻的格子都没有匹配字符串中下标为pathLength+1的字符，表明当前路径字符串中下标为pathLength的字符在矩阵中的定位不正确，我们需要回到前一个字符串（pathLength-1），然后重新定位。
一直重复这个过程，直到路径字符串上所有字符都在矩阵中找到格式的位置（此时str[pathLength] == ‘ ’）。
class Solution: def hasPath(self, matrix, rows, cols, path): """ :param matrix: 字符矩阵 :param rows: 矩阵行数 :param cols: 矩阵列数 :param path: 需要寻找的路径 :return: """ if len(matrix) != rows * cols or len(matrix) == 0 or rows <= 0 or cols <= 0 or path is None: # 参数校验 return False boolmatrix = [0] * (rows * cols) # 这样乘出来是个矩阵了 pathLength = [0] # 已经找到的路径长度 for y in range(rows): for x in range(cols): if self.findPath(matrix, rows, cols, x, y, path, pathLength, boolmatrix): return True return False def findPath(self, matrix, rows, cols, x, y, path, pathLength, boolmatrix): """ :param x: 当前位置的横坐标（对应列数【！】） :param y: :param path: :param pathLength: 当前路径寻找到了的长度 :param boolmatrix: 布尔矩阵数组，访问标志数组，字符在路径中：该位置标为true :return: """ if pathLength[0] == len(path): # 当前路径长度已经等于字符串长度了，就是已经全部找完了 return True nextPath = False # 参数校验：1、位置坐标不超过行列数 # 2、当前位置字符等于路径中对应位置的字符 # 3、当前位置未存在于当前已找到的路径中 if 0 <= x < cols and 0 <= y < rows and matrix[y * cols + x] == path[pathLength[0]] and not boolmatrix[y * cols + x]: boolmatrix[y * cols + x] = True pathLength[0] += 1 # 找周围的有没有下一个字符 nextPath = self.findPath(matrix, rows, cols, x - 1, y, path, pathLength, boolmatrix) or self.findPath(matrix, rows, cols, x + 1, y, path, pathLength, boolmatrix) or self.findPath(matrix, rows, cols, x, y - 1, path, pathLength, boolmatrix) or self.findPath(matrix, rows, cols, x, y + 1, path, pathLength, boolmatrix) if not nextPath: # 没找到该字符，回溯到上一个，布尔标记矩阵中对应的位置标为false pathLength[0] -= 1 boolmatrix[y * cols + x] = False return nextPath
遇到的问题：
1、提示：string index out of range
原因：findPath中，x和y分别表示当前所找字符的横坐标、纵坐标，但是！横坐标代表的是列数，所以参数判断的时候，应该是x<cols，横坐标的值要小于列数