『剣指offer』【マトリックス中の経路】(python版)

タイトルの説明:行列に文字列のすべての文字を含むパスがあるかどうかを判断するために関数を設計してください.パスは、マトリクス内の任意の格子から開始できます.各ステップは、マトリクス内で左、右、上、下に1つの格子を移動できます.1つのパスがマトリクス内の格子を通過した場合、その後この格子に入ることはできません.例えば、a b c e s f c s a d e eのような3 X 4行列には文字列「bcced」の経路が含まれているが、行列の最初の文字bが行列の最初の行の2番目の格子を占めた後、経路が再び格子に入ることができないため、行列には「abcb」の経路が含まれていない.
構想:本題は遡及法を用いた典型的な問題である.文字行列における経路の始点を特定できないため、行列において任意の1つを始点として探索し、求めた経路が存在するか否かを判断する.また、現在の位置文字がパスに含まれているかどうかを確認するために、文字マトリクスと同じサイズのフラグ配列も必要です.マトリクスで見つかったi番目の文字も、パスのi番目の位置の文字に対応しているに違いない.
具体的な実装については、コードを参照してください.

    def hasPath(self, matrix, rows, cols, path):
        #     
        if len(matrix) == 0 or len(matrix) != rows * cols or len(path) == 0:
            return False
        visited = [False] * len(matrix)
        pathlength = [0]
        for i in range(rows):
            for j in range(cols):
                #                  
                if self.haspath(matrix, rows, cols, path, j, i, visited, pathlength):
                    return True
        return False

    #       （x,y）              
    def haspath(self, matrix, rows, cols, path, x, y, visited, pathlength):
        '''
        :param matrix:    
        :param rows:     
        :param cols:     
        :param path:       
        :param x:        (    )
        :param y:        (    )
        :param visited:      
        :param pathlength:         
        :return:      
        '''
        if pathlength[0] == len(path):
            return True
        curhaspath = False
        #     ：1、           2、                   3、                 
        if 0 <= x < cols and 0 <= y < rows \
                and matrix[y * cols + x] == path[pathlength[0]] \
                and not visited[y * cols + x]:

            visited[y * cols + x] = True
            pathlength[0] += 1
            #     ，  ，  ，        ，             
            curhaspath = self.haspath(matrix, rows, cols, path, x - 1, y, visited, pathlength) \
                         or self.haspath(matrix,
                                         rows,
                                         cols,
                                         path,
                                         x, y - 1,
                                         visited,
                                         pathlength) \
                         or self.haspath(
                matrix, rows, cols, path, x + 1, y, visited, pathlength) \
                         or self.haspath(matrix, rows, cols, path,
                                         x, y + 1, visited,
                                         pathlength)
            #          ，         
            if not curhaspath:
                pathlength[0] -= 1
                visited[y * cols + x] = False
        return curhaspath