开始学算法（刷算法题）过程记录 11

题目描述：请设计一个函数，用来判断在一个n乘m的矩阵中是否存在一条包含某长度为len的字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 例如 

矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。

解题思路：使用回溯法。回溯法适合由多个步骤组成的问题，并且每个步骤都有多个选项。当我们在某一步选择了其中一个选项时，就进入下一步，然后又面临新的选项。新选项不满足时回溯到上一步。

本题思路如下图所示，查找顺序为左右上下

做完上图发现牛客网解题有很好的gif演示图。

算法实现：

做完这题发现还是不是很理解回溯法，下面是看了一些学习资料后的思路过程。

参考于：https://www.bilibili.com/video/BV1P5411N7Xc 传送门

回溯法是一种穷举的办法。

问题：有一个棋盘，1行能放1个棋子，一共有多少种放法。

寻找棋子摆放方式，其实就是在遍历这棵树。走到叶子结点就相当于获得了一个可行解。

遍历多叉树的框架：

听了这个视频讲解可以知道，递归的结果会用一个数组存储起来，每到叶子结点返回一次这个数组，所以需要撤销选择，为下一次结果空出位置，如下图。

那么问题来了在上面代码实现的时候也有一段撤销结果的代码：

matrix[row][col]=temp

这里并不需要存储路径，为什么要撤销结果呢？

经过思考后明白了，不管存不存储路径，都需要撤回一步。如果没有撤回的操作，他就只能遍历一条子树然后无法后退了。

思考了一段时间还是无法理解。决定先从简单的入手。

前面提到回溯算法是遍历一颗多叉树的过程，而且回溯算法代码框架与多叉树遍历代码框架类似。所以我觉得可以先从多叉树遍历开始入手。

多叉树遍历参考于：https://www.csdn.net/tags/MtTaMgysMjQyMTc0LWJsb2cO0O0O.html

        首先传入根节点-节点存在-输出节点名-节点有子节点且子节点长度大于0-遍历下一层所有子节点-所有子节点再执行一遍traverseTree函数。他会一直往下执行，直到倒数第二步碰到叶子节点传入-叶子结点没有childrenn属性-再传入为null-函数结束。

        这个函数和之前的斐波那契数列递归解法很像，调用过程像一个三角形(像回调地狱)，斐波那契数列还需要从最里面的函数得到返回值才能继续外层函数调用，上面的函数会等待最里面的函数返回那个1然后1+1。

        这个多叉树遍历的调用过程像只有一半三角形，运行到最后没有值，理论上运行到一半终止得到的也是部分正确的结果，而斐波那契递归调用如果中途终止得不到结果。有点像击鼓传花，第一个人拿到鼓，后面一个人看到前面的人敲鼓了自己也拿出鼓敲一下，直到后面没有人。

        回溯算法的框架多了一些步骤，第一部分if结束条件多了添加路径，因为回溯算法走到节点相当于获得了一个解，所以这一部分用于在走到叶子结点的时候保存解。第二部分是回溯算法的核心部分我一直不是很理解，我多次观看视频的22分钟左右的部分。中间部分的backtrack(路径,选择列表)。

        首先要理解什么情况下会到撤销选择这一步，进入下一行要是都放不了，他就回到这里，然后撤回，然后返回上一层循环。返回上一个循环如果没有撤销选择 那么在上一层做选择的时候，下一层还放着上一个循环放的Q，这就会导致错误了。