劍指offer：矩陣中的路徑

題目描述
請設(shè)計一個函數(shù)，用來判斷在一個矩陣中是否存在一條包含某字符串所有字符的路徑。路徑可以從矩陣中的任意一個格子開始，每一步可以在矩陣中向左，向右，向上，向下移動一個格子。如果一條路徑經(jīng)過了矩陣中的某一個格子，則之后不能再次進(jìn)入這個格子。 例如 a b c e s f c s a d e e 這樣的3 X 4 矩陣中包含一條字符串"bcced"的路徑，但是矩陣中不包含"abcb"路徑，因為字符串的第一個字符b占據(jù)了矩陣中的第一行第二個格子之后，路徑不能再次進(jìn)入該格子。

class Solution:
    """
    判斷迷宮/棋盤內(nèi)是否有解的一個方法是回溯法。

    當(dāng)位于坐標(biāo)(i, j)的時候，如果當(dāng)前位置有效，則往所有可能的方向都走一步，否則回退到上一步

    回溯一般可以基于遞歸或棧來實現(xiàn)。
    以遞歸為例，若當(dāng)前位置合法(未被剪枝去掉)，則從當(dāng)前位置出發(fā)，繼續(xù)探索可能的位置，否則回退到
    上一個位置
    """
    def hasPath(self, matrix, path):
        def helper(path_, row, col):
            """
            由(row, col)出發(fā)，探索所有可能的位置(遞)，
            當(dāng)發(fā)現(xiàn)有解或需要剪枝的時候就返回上一步(歸)
            :param path_: 剩余待查找的路徑
            :param row: 當(dāng)前所在的行
            :param col:當(dāng)前所在的列
            :return: 是否有解
            """
            if not path_:
                return True
            if (row >= rows or row < 0 or col >= cols or col < 0
                    or matrix[row][col] != path_[0]):
                return False

            temp = matrix[row][col]  # 記錄當(dāng)前位置的值，以便回溯的時候還原
            matrix[row][col] = '#'  # 標(biāo)記為已走過
            # 探索左右可能的位置(子節(jié)點)
            res = (helper(path_[1:], row, col + 1)
                   or helper(path_[1:], row, col - 1)
                   or helper(path_[1:], row + 1, col)
                   or helper(path_[1:], row - 1, col))
            matrix[row][col] = temp  # 回溯時還原前面的標(biāo)記，因為回溯后這個點相當(dāng)于沒走過
            return res

        if not path:
            return True
        if not matrix:
            return False
        rows, cols = len(matrix), len(matrix[0])

        for i in range(rows):
            for j in range(cols):
                # 這里可以先判斷是否符合起點再進(jìn)行遞歸也可以直接遞歸，但是先判斷可以減少開銷
                if matrix[i][j] == path[0]:
                    if helper(path, i, j):
                        return True

        return False