题目：请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。
路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。
如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。例如 ：
a b c e
c f c s
a d e e
矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，
因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。
这道题思路其实是很简单的，就是回溯法。
先找到第一个匹配的字符，然后从它的四周找下一个字符，如果找到了，接着往下找。
如果没找到，那么返回上一个字符从另一个方向找。
比如找"bfce"，先找到b，在第一行的第二个，再找下一个字符'f'。
然后b的左方'a'不是，下方'f'是。那么再找下一个'c'。
'f'的左方'c'是，再找下一个'e'。
'c'的左边没有，下边是'a'，不对。右边'f'是访问过的。注意，题目中要求一条路径不能有循环，所以先判断的是'f'有没有访问过。上方'a'也不对。
所以这个节点是错误的。
返回'f'节点，刚才只找了'f'的左边，现在找下面'd'，不对。右边'c'，匹配。
再从'c'往下找'e'，左边访问过，下面'e'匹配。目标字符串找完了。返回结果存在该路径。
思路是很简单的，但是如何实现代码还是有一点难度的，怎样找到一条路径，怎么确定没有重复访问，还是需要思考的。
python代码如下：
def has_path(matrix, path):
rows = len(matrix)
cols = len(matrix[0])
if not matrix or rows < 0 or cols < 0 or path is None: # 参数合法性检测
return False
mark_matrix = [0] * (rows * cols) # 表示matrix中的字符是已被访问，因为题目中路径必须是单向的
path_index = 0 # 表示当前正在查找path中的第几位
for row in range(rows):
for col in range(cols):
if has_path_core(matrix, rows, cols, row, col, path, path_index, mark_matrix):
return True
return False
def has_path_core(matrix, rows, cols, row, col, path, path_index, mark_matrix):
if path_index == len(path): # 表示path中所有字符都已匹配，则返回True
return True
hp = False
# 1.参数合法性检查 2.matrix[row][col]和path[path_index]匹配 3.当前位置没有被访问过
if 0 <= row < rows and 0 <= col < cols and matrix[row][col] == path[path_index] and \
not mark_matrix[row * cols + col]:
path_index += 1 # 匹配path中的下一个字符
mark_matrix[row * cols + col] = True # 当前位置已被访问过，不可再次访问
# 递归查找四周的字符
hp = has_path_core(matrix, rows, cols, row + 1, col, path, path_index, mark_matrix) or \
has_path_core(matrix, rows, cols, row - 1, col, path, path_index, mark_matrix) or \
has_path_core(matrix, rows, cols, row, col + 1, path, path_index, mark_matrix) or \
has_path_core(matrix, rows, cols, row, col - 1, path, path_index, mark_matrix)
# 如果四周都没有和path[path_index]相匹配的，则当前路径错误，退回到path中的上一个字符，并将该位置置为可读
if not hp:
path_index -= 1
mark_matrix[row * cols + col] = False
return hp
if __name__ == '__main__':
path = 'bfce'
matrix = [['a', 'b', 't', 'g'], ['c', 'f', 'c', 's'], ['j', 'd', 'e', 'h']]
print(has_path(matrix, path))
代码中已经加了比较详细的注释，有些地方还是需要仔细思考。用个实际的例子，跟着代码的流程走一走。
