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

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

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

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

    回溯一般可以基于遞歸或棧來實(shí)現(xiàn)。
    以遞歸為例，若當(dāng)前位置合法(未被剪枝去掉)，則從當(dāng)前位置出發(fā)，繼續(xù)探索可能的位置，否則回退到
    上一個(gè)位置
    """
    def hasPath(self, matrix, path):
        def helper(path_, row, col):
            """
            由(row, col)出發(fā)，探索所有可能的位置(遞)，
            當(dāng)發(fā)現(xiàn)有解或需要剪枝的時(shí)候就返回上一步(歸)
            :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)前位置的值，以便回溯的時(shí)候還原
            matrix[row][col] = '#'  # 標(biāo)記為已走過
            # 探索左右可能的位置(子節(jié)點(diǎn))
            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  # 回溯時(shí)還原前面的標(biāo)記，因?yàn)榛厮莺筮@個(gè)點(diǎn)相當(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):
                # 這里可以先判斷是否符合起點(diǎn)再進(jìn)行遞歸也可以直接遞歸，但是先判斷可以減少開銷
                if matrix[i][j] == path[0]:
                    if helper(path, i, j):
                        return True

        return False

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

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

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站設(shè)計(jì)、關(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)請盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)