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

成都創新互聯公司-專業網站定制、快速模板網站建設、高性價比承留網站開發、企業建站全套包干低至880元,成熟完善的模板庫,直接使用。一站式承留網站制作公司更省心,省錢,快速模板網站建設找我們，業務覆蓋承留地區。費用合理售后完善，10年實體公司更值得信賴。

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

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

    回溯一般可以基于遞歸或棧來實現。
    以遞歸為例，若當前位置合法(未被剪枝去掉)，則從當前位置出發，繼續探索可能的位置，否則回退到
    上一個位置
    """
    def hasPath(self, matrix, path):
        def helper(path_, row, col):
            """
            由(row, col)出發，探索所有可能的位置(遞)，
            當發現有解或需要剪枝的時候就返回上一步(歸)
            :param path_: 剩余待查找的路徑
            :param row: 當前所在的行
            :param col:當前所在的列
            :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]  # 記錄當前位置的值，以便回溯的時候還原
            matrix[row][col] = '#'  # 標記為已走過
            # 探索左右可能的位置(子節點)
            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  # 回溯時還原前面的標記，因為回溯后這個點相當于沒走過
            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):
                # 這里可以先判斷是否符合起點再進行遞歸也可以直接遞歸，但是先判斷可以減少開銷
                if matrix[i][j] == path[0]:
                    if helper(path, i, j):
                        return True

        return False

另外有需要云服務器可以了解下創新互聯cdcxhl.cn，海內外云服務器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務器、裸金屬服務器、高防服務器、香港服務器、美國服務器、虛擬主機、免備案服務器”等云主機租用服務以及企業上云的綜合解決方案，具有“安全穩定、簡單易用、服務可用性高、性價比高”等特點與優勢，專為企業上云打造定制，能夠滿足用戶豐富、多元化的應用場景需求。

網頁名稱：劍指offer：矩陣中的路徑-創新互聯
標題URL：http://www.yijiale78.com/article16/psidg.html

成都網站建設公司_創新互聯，為您提供網站設計、關鍵詞優化、網站營銷、靜態網站、定制網站、品牌網站制作

廣告

聲明：本網站發布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創新互聯