矩阵中的路径

题目：用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。
解答：回溯经典例题，
回溯思想解题框架：

回溯
result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return
    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

本题只要求出是否满足，而没有要求求出满足路径，所以返回True或False即可。

# -*- coding:utf-8 -*-
class Solution:
    def hasPath(self, matrix, rows, cols, path):
        # write code here
        flag = [0 for i in range(rows*cols)]
        for i in range(rows):
            for j in range(cols):
                if self.helper(matrix,rows,cols,i,j,path,0,flag):
                    return True
        return False

    def helper(self,matrix,rows,cols,i,j,s,k,flag):
        # i 表示行 j 表示列 s 表示需要的字符串 k表示现在字符串长度 flag 表示位置是否被访问
        index = i*cols+j
        if i<0 or i>=rows or j<0 or j>=cols or matrix[index]!=s[k] or flag[index] == 1:
            return False
        if k == len(s)-1:
            return True
        flag[index] = 1
        if self.helper(matrix,rows,cols,i+1,j,s,k+1,flag) or self.helper(matrix,rows,cols,i,j+1,s,k+1,flag) or self.helper(matrix,rows,cols,i-1,j,s,k+1,flag) or self.helper(matrix,rows,cols,i,j-1,s,k+1,flag):
            return True
        flag[index] == 0
        return False