• 利用回溯的方法
1. 设置visited矩阵，当走过i，j点时，将此点设置为1，因为不能重复进入一个格子
2. 如果第ij个点与path中的字符一样且未走过，则暂时进入这个格子
3. 向四周搜寻下一步的走法，若无解，则证明上一个path路径不对，退回到前一个字符
4. 若正确，则重复上述过程，返回haspath
class Solution:
def hasPath(self, matrix, rows, cols, path):
# write code here
if not matrix or not path:
return False
visited = [0]*cols*rows
pathLenth = 0
for i in range(rows):
for j in range(cols):
if self.hasPathCore(matrix, i, j, rows, cols, path, pathLenth, visited):
return True
return False
def hasPathCore(self, matrix, i, j, rows, cols, path, pathLenth, visited):
if pathLenth == len(path):
return True
hasPath = False
if 0 <= i < rows and 0 <= j < cols and matrix[i*cols+j] == path[pathLenth] and not visited[i*cols+j]:
pathLenth += 1
visited[i*cols+j] = 1
hasPath = self.hasPathCore(matrix, i, j-1, rows, cols, path, pathLenth, visited) or \
self.hasPathCore(matrix, i-1, j, rows, cols, path, pathLenth, visited) or\
self.hasPathCore(matrix, i, j+1, rows, cols, path, pathLenth, visited) or\
self.hasPathCore(matrix, i+1, j, rows, cols, path, pathLenth, visited)
if not hasPath:
pathLenth -= 1
visited[i*cols+j] = 0
return hasPath