题目描述
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则之后不能再次进入这个格子。 例如 a b c e s f c s a d e e 这样的3 X 4 矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。
思路
这道题使用回溯法来解决，也是深搜的一种。 对于递归，通常有三个地方需要考虑，
1 是递归的定义，把问题转化为递归，要递归哪些方面。
2 是递归的拆解，如果把问题实际转化成递归问题。
3 是递归的出口，当递归发现解之后，如何返回，如何一步一步返回上一层。
在使用回溯方法的时候，通常会有一个栈来记录搜索过的正确的路径，到达当前一个状态后，会先尝试把当前的节点/状态入栈，如果无解再返回。
针对本问题，具体思路是： 遍历矩阵，找到开头后，开始递归的对问题求解。用index来记录目标字符串的位置，寻找到解以后，就把index+1，尝试无解后回溯到index-1. 因为题目要求同一个格子不允许进入两次，所以再额外构建一个二维矩阵用来记录每个格子是否被访问过。
代码
# -*- coding:utf-8 -*-
class Solution:
def hasPath(self, matrix, rows, cols, path):
#特殊情况判断
if matrix is None or rows<1 or cols <1 or path is None:
return False
#题目输入不是二维数组，将长序列变成2维数组
temp_matrix =[['' for j in range(cols)] for i in range(rows)]
count=0
for i in range(rows):
for j in range(cols):
temp_matrix[i][j]=matrix[count]
count+=1
#分别是访问矩阵和下标
visited = [[0]* cols for i in range(rows)]
index = 0
for i in range(rows):
for j in range(cols):
if temp_matrix[i][j] == path[0]: #找到符合第一个开头的
if self.helper(temp_matrix,rows,cols,visited,path,index,i,j):
return True
return False
def helper(self,matrix,rows,cols,visited,path,index,row_index,column_index):
if len(path) == index: #最后的情况，证明前一个就是path最后了
return True
flag = False
if (row_index >=0 and row_index < rows and column_index >=0
and column_index <cols and matrix[row_index][column_index] == path[index]
and not visited[row_index][column_index]): #判别情况，包括边界大小，目标值相等，没有访问过
index = index+1
visited[row_index][column_index] = True
flag1 = self.helper(matrix,rows,cols,visited,path,index,row_index+1,column_index)
flag2 = self.helper(matrix,rows,cols,visited,path,index,row_index-1,column_index)
flag3 = self.helper(matrix,rows,cols,visited,path,index,row_index,column_index+1)
flag4 = self.helper(matrix,rows,cols,visited,path,index,row_index,column_index-1)
flag = flag1 or flag2 or flag3 or flag4 #4个flag表示按四个方向寻找
if flag is False: #寻找错误，回溯到前一个地方
index = index -1
visited[row_index][column_index] = False
return flag
这里有一个Python初始化二维数组的小技巧，记录一下
N = [[0]*3 for i in range(10)]
matrix =[[0 for j in range(cols)] for i in range(rows)]
