目錄

創(chuàng)新互聯(lián)是專業(yè)的凌河網(wǎng)站建設(shè)公司，凌河接單;提供網(wǎng)站設(shè)計、成都網(wǎng)站設(shè)計,網(wǎng)頁設(shè)計,網(wǎng)站設(shè)計,建網(wǎng)站,PHP網(wǎng)站建設(shè)等專業(yè)做網(wǎng)站服務(wù);采用PHP框架,可快速的進行凌河網(wǎng)站開發(fā)網(wǎng)頁制作和功能擴展;專業(yè)做搜索引擎喜愛的網(wǎng)站,專業(yè)的做網(wǎng)站團隊,希望更多企業(yè)前來合作!

1.?矩陣中的路徑

1.1?題目描述

1.2?基礎(chǔ)知識

1.3?思路分析

1.4?小試牛刀

---

1.?矩陣中的路徑

原題鏈接：

劍指 Offer 12. 矩陣中的路徑 - 力扣（LeetCode）https://leetcode.cn/problems/ju-zhen-zhong-de-lu-jing-lcof/submissions/

1.1?題目描述

給定一個?m x n 二維字符網(wǎng)格?board 和一個字符串單詞?word 。如果?word 存在于網(wǎng)格中，返回 true ；否則，返回 false 。

單詞必須按照字母順序，通過相鄰的單元格內(nèi)的字母構(gòu)成，其中“相鄰”單元格是那些水平相鄰或垂直相鄰的單元格。同一個單元格內(nèi)的字母不允許被重復使用。

1.2?基礎(chǔ)知識

回溯法可以看成蠻力法的升級，他從解決問題每一步的所有可能選項里系統(tǒng)地選擇出一個可行的解決方案?；厮莘ǚ浅＿m合由多個步驟組成的問題，并且每個步驟都有多個選項。當我們在某一步選擇了其中一個選項時，就進入下一步，然后又面臨新的選擇。我們就這樣重復選擇直到達到最終的狀態(tài)。

用回溯法解決問題的所有選項可以形象地用樹狀結(jié)構(gòu)表示。在某一步可能有n個可能的選項，那么該步驟可以看成是樹狀結(jié)構(gòu)中的一個節(jié)點，每個選項看成樹中節(jié)點的連接線，經(jīng)過這些連接線到達該節(jié)點的n個子節(jié)點。樹的葉節(jié)點對應(yīng)著最終的狀態(tài)。如果在葉節(jié)點的狀態(tài)滿足題目的約束條件，那我們就找到了一個可行的解決方案。

如果不滿足條件就回溯到上一個節(jié)點，再嘗試其他的選項。如果所有節(jié)點的所有選項都已經(jīng)嘗試過依然不能達到滿足約束條件的終結(jié)狀態(tài)，則該問題無解。

通?；厮菟惴ㄟm合用遞歸實現(xiàn)。當我們到達某一個節(jié)點時，嘗試所有可能的選項并在滿足條件的前提下遞歸地抵達下一個節(jié)點。

1.3?思路分析

有了以上的基礎(chǔ)知識，我們以一個具體的例子對該題進行分析。

以輸入矩陣? ?A? ? B? ?C? ?E

S? ? F?? C? ?S

A? ? D? ?E? ? F? ? ，輸入字符串 "BFCE"為例。

首先我們需要遍歷輸入的矩陣，把每一個下標的位置都作為一次遞歸的起點，嘗試往下遞歸。這時在遞歸函數(shù)的內(nèi)部我們就需要對進入遞歸函數(shù)的下標做合法性判斷，并且與輸入字符串的第一個字符進行比較，若與字符串的第一個字符相等，我們就找到了可以繼續(xù)往下遞歸的位置啦。為此在遞歸函數(shù)的參數(shù)上需要一個下標變量，能夠在遞歸的過程中，逐步遍歷到輸入字符串的每一個字符。（找到解題路徑的依據(jù)就是匹配到輸入字符串的每一個字符嘛）

對于上述例子，遍歷輸入字符串的下標變量不妨設(shè)為index，初始時index為0，對應(yīng)輸入的字符B，當我們嘗試遞歸B這個位置時，他與index指向的字符相等，我們就讓下一層遞歸時index的值加1指向下一個查找的字符，即嘗試去找到?F這個字符。

另外對于一個位置的遞歸，根據(jù)題目要求走過的位置是不能夠再走的，因此遞歸時，需要對當前遞歸位置的矩陣中的字符進行記錄后，對其進行修改，比如修改為 '#'，以此來防止出現(xiàn)往回走的情況。同時無論找沒找到解題的路線在回溯的過程中都需要將修改過的字符改回來（通過保存的記錄來修改），不然就無法進行矩陣中下一個位置最開始的查找啦（遍歷矩陣從矩陣中的每一個位置嘗試遞歸查找嘛）。

根據(jù)最開始的基礎(chǔ)知識，我們假設(shè)對于每一個位置的查找是按照上，下，左，右的順序，畫出一個樹狀圖來分析。分析例子還是：

以輸入矩陣? ?A? ? B? ?C? ?E

S? ? F?? C? ?S

A? ? D? ?E? ? F? ? ，輸入字符串 "BFCE"為例。

在對上下左右的方向查找index+1指向的字符時，只要我們找到一條解題的路即可，假設(shè)有多條解題路線，我們改變上下左右這四個方向的順序，查找到的結(jié)果可能是不同的。

當index指向的字符正好為strlen(輸入的字符串) - 1?時，就找到了解題的路徑，注意對遞歸進來的坐標進行合法性判斷的語句在該語句之前確保了已經(jīng)找到了輸入字符串的最后一個字符。

我們對上下左右方向的遞歸采取? | |? 的邏輯運算返回最終的結(jié)果，只要一個方向向下的遞歸找到了解題的路徑，就能夠逐層返回true，完成解題。

bool recurison(char** board, int boardSize, int* boardColSize, char* word, int i, int j, int index)
{
    //對遞歸進來的坐標進行合法性判斷，并且對該位置的字符與index指向的字符判斷，不相等就結(jié)束當            
      前層的遞歸
    if(i<0||i>=boardSize||j<0||j>=*boardColSize|| board[i][j] != word[index])
    {
        return false;
    }
    //如果執(zhí)行此條語句證明找到了解題的路線
    if(index == strlen(word) - 1)
    {
        return true;
    }
    //記錄遞歸當前層位置的字符，方便后續(xù)回溯時將被修改過的字符換回來
    char tmp = board[i][j];
    //走過的位置進行修改，不允許再次遞歸
    board[i][j] = '#';
    //對該位置的上下左右方向的字符進行查找判斷，index加一表示將要查找的字符
    bool ret = recurison(board, boardSize, boardColSize,word, i - 1,j,index+1) || 
               recurison(board, boardSize, boardColSize,word, i + 1,j,index+1) ||
               recurison(board, boardSize, boardColSize,word, i,j + 1,index+1) ||
               recurison(board, boardSize, boardColSize,word, i,j - 1,index+1);
    //回溯時改回來被修改的字符
    board[i][j] = tmp;
    //返回當前遞歸層的結(jié)果
    return ret;
}

bool exist(char** board, int boardSize, int* boardColSize, char* word){
    int i = 0;
    int j = 0;
    for(i=0;i

1.4?小試牛刀

下面是迷宮問題1,和迷宮問題2

對于這兩個題我以前的博客有講解，我發(fā)現(xiàn)自己會做了，能講清楚還是有點難度的，歡迎大佬們發(fā)表建議和意見

力扣https://leetcode.cn/tag/backtracking/problemset/地下迷宮_滴滴筆試題_?？途W(wǎng)地下迷宮https://www.nowcoder.com/questionTerminal/571cfbe764824f03b5c0bfd2eb0a8ddf

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

本文標題：劍指offer----C語言版----第八天-創(chuàng)新互聯(lián)
文章起源：http://chinadenli.net/article24/ccodje.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供品牌網(wǎng)站建設(shè)、靜態(tài)網(wǎng)站、網(wǎng)站導航、網(wǎng)站營銷、網(wǎng)站設(shè)計公司、網(wǎng)頁設(shè)計公司

廣告

聲明：本網(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)