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

矩陣中包含一條字符串"bcced"的路徑，但是矩陣中不包含"abcb"路徑，因為字符串的第一個字符b占據(jù)了矩陣中的第一行第二個格子之后，路徑不能再次進入該格子。

解題思路：使用回溯法?；厮莘ㄟm合由多個步驟組成的問題，并且每個步驟都有多個選項。當我們在某一步選擇了其中一個選項時，就進入下一步，然后又面臨新的選項。新選項不滿足時回溯到上一步。

本題思路如下圖所示，查找順序為左右上下

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

算法實現(xiàn)：

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

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

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

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

尋找棋子擺放方式，其實就是在遍歷這棵樹。走到葉子結點就相當于獲得了一個可行解。

遍歷多叉樹的框架：

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

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

matrix[row][col]=temp

這里并不需要存儲路徑，為什么要撤銷結果呢？

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

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

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

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

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

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

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

????????回溯算法的框架多了一些步驟，第一部分if結束條件多了添加路徑，因為回溯算法走到節(jié)點相當于獲得了一個解，所以這一部分用于在走到葉子結點的時候保存解。第二部分是回溯算法的核心部分我一直不是很理解，我多次觀看視頻的22分鐘左右的部分。中間部分的backtrack(路徑,選擇列表)。

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