題目描述：請(qǐng)?jiān)O(shè)計(jì)一個(gè)函數(shù)，用來判斷在一個(gè)n乘m的矩陣中是否存在一條包含某長度為len的字符串所有字符的路徑。路徑可以從矩陣中的任意一個(gè)格子開始，每一步可以在矩陣中向左，向右，向上，向下移動(dòng)一個(gè)格子。如果一條路徑經(jīng)過了矩陣中的某一個(gè)格子，則該路徑不能再進(jìn)入該格子。 例如?

矩陣中包含一條字符串"bcced"的路徑，但是矩陣中不包含"abcb"路徑，因?yàn)樽址牡谝粋€(gè)字符b占據(jù)了矩陣中的第一行第二個(gè)格子之后，路徑不能再次進(jìn)入該格子。

解題思路：使用回溯法?；厮莘ㄟm合由多個(gè)步驟組成的問題，并且每個(gè)步驟都有多個(gè)選項(xiàng)。當(dāng)我們?cè)谀骋徊竭x擇了其中一個(gè)選項(xiàng)時(shí)，就進(jìn)入下一步，然后又面臨新的選項(xiàng)。新選項(xiàng)不滿足時(shí)回溯到上一步。

本題思路如下圖所示，查找順序?yàn)樽笥疑舷?/p>

做完上圖發(fā)現(xiàn)牛客網(wǎng)解題有很好的gif演示圖。

算法實(shí)現(xiàn)：

做完這題發(fā)現(xiàn)還是不是很理解回溯法，下面是看了一些學(xué)習(xí)資料后的思路過程。

參考于：https://www.bilibili.com/video/BV1P5411N7Xc?傳送門

回溯法是一種窮舉的辦法。

問題：有一個(gè)棋盤，1行能放1個(gè)棋子，一共有多少種放法。

尋找棋子擺放方式，其實(shí)就是在遍歷這棵樹。走到葉子結(jié)點(diǎn)就相當(dāng)于獲得了一個(gè)可行解。

遍歷多叉樹的框架：

聽了這個(gè)視頻講解可以知道，遞歸的結(jié)果會(huì)用一個(gè)數(shù)組存儲(chǔ)起來，每到葉子結(jié)點(diǎn)返回一次這個(gè)數(shù)組，所以需要撤銷選擇，為下一次結(jié)果空出位置，如下圖。

那么問題來了在上面代碼實(shí)現(xiàn)的時(shí)候也有一段撤銷結(jié)果的代碼：

matrix[row][col]=temp

這里并不需要存儲(chǔ)路徑，為什么要撤銷結(jié)果呢？

經(jīng)過思考后明白了，不管存不存儲(chǔ)路徑，都需要撤回一步。如果沒有撤回的操作，他就只能遍歷一條子樹然后無法后退了。

思考了一段時(shí)間還是無法理解。決定先從簡單的入手。

前面提到回溯算法是遍歷一顆多叉樹的過程，而且回溯算法代碼框架與多叉樹遍歷代碼框架類似。所以我覺得可以先從多叉樹遍歷開始入手。

多叉樹遍歷參考于：https://www.csdn.net/tags/MtTaMgysMjQyMTc0LWJsb2cO0O0O.html

????????首先傳入根節(jié)點(diǎn)-節(jié)點(diǎn)存在-輸出節(jié)點(diǎn)名-節(jié)點(diǎn)有子節(jié)點(diǎn)且子節(jié)點(diǎn)長度大于0-遍歷下一層所有子節(jié)點(diǎn)-所有子節(jié)點(diǎn)再執(zhí)行一遍traverseTree函數(shù)。他會(huì)一直往下執(zhí)行，直到倒數(shù)第二步碰到葉子節(jié)點(diǎn)傳入-葉子結(jié)點(diǎn)沒有childrenn屬性-再傳入為null-函數(shù)結(jié)束。

????????這個(gè)函數(shù)和之前的斐波那契數(shù)列遞歸解法很像，調(diào)用過程像一個(gè)三角形(像回調(diào)地獄)，斐波那契數(shù)列還需要從最里面的函數(shù)得到返回值才能繼續(xù)外層函數(shù)調(diào)用，上面的函數(shù)會(huì)等待最里面的函數(shù)返回那個(gè)1然后1+1。

????????這個(gè)多叉樹遍歷的調(diào)用過程像只有一半三角形，運(yùn)行到最后沒有值，理論上運(yùn)行到一半終止得到的也是部分正確的結(jié)果，而斐波那契遞歸調(diào)用如果中途終止得不到結(jié)果。有點(diǎn)像擊鼓傳花，第一個(gè)人拿到鼓，后面一個(gè)人看到前面的人敲鼓了自己也拿出鼓敲一下，直到后面沒有人。

????????回溯算法的框架多了一些步驟，第一部分if結(jié)束條件多了添加路徑，因?yàn)榛厮菟惴ㄗ叩焦?jié)點(diǎn)相當(dāng)于獲得了一個(gè)解，所以這一部分用于在走到葉子結(jié)點(diǎn)的時(shí)候保存解。第二部分是回溯算法的核心部分我一直不是很理解，我多次觀看視頻的22分鐘左右的部分。中間部分的backtrack(路徑,選擇列表)。

????????首先要理解什么情況下會(huì)到撤銷選擇這一步，進(jìn)入下一行要是都放不了，他就回到這里，然后撤回，然后返回上一層循環(huán)。返回上一個(gè)循環(huán)如果沒有撤銷選擇 那么在上一層做選擇的時(shí)候，下一層還放著上一個(gè)循環(huán)放的Q，這就會(huì)導(dǎo)致錯(cuò)誤了。