劍指offer：矩陣中的路徑-創(chuàng)新互聯(lián)

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

成都創(chuàng)新互聯(lián)公司-專業(yè)網(wǎng)站定制、快速模板網(wǎng)站建設(shè)、高性價比承留網(wǎng)站開發(fā)、企業(yè)建站全套包干低至880元,成熟完善的模板庫,直接使用。一站式承留網(wǎng)站制作公司更省心,省錢,快速模板網(wǎng)站建設(shè)找我們，業(yè)務覆蓋承留地區(qū)。費用合理售后完善，10年實體公司更值得信賴。
class Solution:
    """
    判斷迷宮/棋盤內(nèi)是否有解的一個方法是回溯法。

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

    回溯一般可以基于遞歸或棧來實現(xiàn)。
    以遞歸為例，若當前位置合法(未被剪枝去掉)，則從當前位置出發(fā)，繼續(xù)探索可能的位置，否則回退到
    上一個位置
    """
    def hasPath(self, matrix, path):
        def helper(path_, row, col):
            """
            由(row, col)出發(fā)，探索所有可能的位置(遞)，
            當發(fā)現(xiàn)有解或需要剪枝的時候就返回上一步(歸)
            :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] = '#'  # 標記為已走過
            # 探索左右可能的位置(子節(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  # 回溯時還原前面的標記，因為回溯后這個點相當于沒走過
            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

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

網(wǎng)頁名稱：劍指offer：矩陣中的路徑-創(chuàng)新互聯(lián)
標題URL：http://muchs.cn/article16/psidg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站設(shè)計、關(guān)鍵詞優(yōu)化、網(wǎng)站營銷、靜態(tài)網(wǎng)站、定制網(wǎng)站、品牌網(wǎng)站制作

廣告

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

成都做網(wǎng)站