剣指offer面接問題12 python版+解析:マトリクスの中の経路

タイトルの説明
1つのマトリクスに文字列のすべての文字を含むパスがあるかどうかを判断する関数を設計してください.パスは、マトリクス内の任意の格子から開始できます.各ステップは、マトリクス内で左、右、上、下に1つの格子を移動できます.1つのパスがマトリクス内の格子を通過した場合、その後この格子に入ることはできません.例えば、a b c e s f c s a d e eのような3 X 4行列には、文字列「bcced」の経路が含まれるが、行列の最初の文字bが行列の最初の行の2番目の格子を占めた後、経路が再び格子に入ることができないため、行列には「abcb」の経路が含まれない.
 
考え方:遡及法
1.行列内の任意の格子を経路の始点とする.マトリクス内の格子の文字がchであり、この格子が経路上のi番目の文字に対応すると仮定する.パス上のi番目の文字がchでない場合、この格子がパス上のi番目の位置にあるはずがない.パス上のi番目の文字がchである場合、隣接する格子に向かってパス上のi+1番目の文字を探します.行列境界上の格子を除いて,他の格子には4つの隣接する格子がある.パス上のすべての文字がマトリクス内で対応する位置を見つけるまで、この手順を繰り返します.
2.遡及法は再帰性を有し、経路はスタックと見なすことができる.マトリクス内で経路の前のn文字の位置を特定した後、n文字目に対応する格子の周囲にn+1文字目が見つからない場合は、経路上でn−1文字目に戻り、n文字を再配置するしかない.
3.パスは繰り返し格子に入ることはできません.また、パスが各格子に入ったかどうかを識別するために、文字行列と同じ大きさのブール値行列を定義する必要があります.

# -*- coding:utf-8 -*-
class Solution:
    def hasPath(self, matrix, rows, cols, path):
        # write code here
        for i in range(rows):
            for j in range(cols):
                if matrix[i*cols+j]==path[0]:
                    if self.find(list(matrix), rows, cols, path[1:],i,j):
                        return True
        return False
    
    def find(self, matrix, rows, cols, path, i, j):
        if not path:
            return True
        matrix[i*cols+j] = "0"
        if j+1=0 and matrix[i*cols+j-1] == path[0]:
            return self.find(matrix, rows, cols, path[1:],i,j-1)
        elif i+1=0 and matrix[(i-1)*cols+j] == path[0]:
            return self.find(matrix, rows, cols, path[1:],i-1,j)