矩阵中的路径

题目描述

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则之后不能再次进入这个格子。 例如 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)]