目錄

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

1.?矩陣中的路徑

1.1?題目描述

1.2?基礎(chǔ)知識(shí)

1.3?思路分析

1.4?小試牛刀

---

1.?矩陣中的路徑

原題鏈接：

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

1.1?題目描述

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

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

1.2?基礎(chǔ)知識(shí)

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

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

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

通常回溯算法適合用遞歸實(shí)現(xiàn)。當(dāng)我們到達(dá)某一個(gè)節(jié)點(diǎn)時(shí)，嘗試所有可能的選項(xiàng)并在滿足條件的前提下遞歸地抵達(dá)下一個(gè)節(jié)點(diǎn)。

1.3?思路分析

有了以上的基礎(chǔ)知識(shí)，我們以一個(gè)具體的例子對(duì)該題進(jìn)行分析。

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

S? ? F?? C? ?S

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

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

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

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

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

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

S? ? F?? C? ?S

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

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

當(dāng)index指向的字符正好為strlen(輸入的字符串) - 1?時(shí)，就找到了解題的路徑，注意對(duì)遞歸進(jìn)來(lái)的坐標(biāo)進(jìn)行合法性判斷的語(yǔ)句在該語(yǔ)句之前確保了已經(jīng)找到了輸入字符串的最后一個(gè)字符。

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

bool recurison(char** board, int boardSize, int* boardColSize, char* word, int i, int j, int index)
{
    //對(duì)遞歸進(jìn)來(lái)的坐標(biāo)進(jìn)行合法性判斷，并且對(duì)該位置的字符與index指向的字符判斷，不相等就結(jié)束當(dāng)            
      前層的遞歸
    if(i<0||i>=boardSize||j<0||j>=*boardColSize|| board[i][j] != word[index])
    {
        return false;
    }
    //如果執(zhí)行此條語(yǔ)句證明找到了解題的路線
    if(index == strlen(word) - 1)
    {
        return true;
    }
    //記錄遞歸當(dāng)前層位置的字符，方便后續(xù)回溯時(shí)將被修改過(guò)的字符換回來(lái)
    char tmp = board[i][j];
    //走過(guò)的位置進(jìn)行修改，不允許再次遞歸
    board[i][j] = '#';
    //對(duì)該位置的上下左右方向的字符進(jìn)行查找判斷，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);
    //回溯時(shí)改回來(lái)被修改的字符
    board[i][j] = tmp;
    //返回當(dāng)前遞歸層的結(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?小試牛刀

下面是迷宮問(wèn)題1,和迷宮問(wèn)題2

對(duì)于這兩個(gè)題我以前的博客有講解，我發(fā)現(xiàn)自己會(huì)做了，能講清楚還是有點(diǎ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海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

標(biāo)題名稱：劍指offer----C語(yǔ)言版----第八天-創(chuàng)新互聯(lián)
地址分享：http://weahome.cn/article/ccodje.html