回溯法——面试题矩阵中的路径(一)

这里写目录标题
回溯法介绍
回溯法应用（实例化）
回溯法介绍
1.1
回溯法是蛮力法的升级版，它从解决问题每一步的所有可能选项里系统的选择一个可行的解决方案。
1.2
回溯法非常适合由多个步骤组成的问题，并且每个步骤都有多个选项。当我们在某一步做出一个选择时，就进到下一步了，如果不符合题目条件，就回溯到原来的步骤进行新的选择，如果这步的选择还没有符合条件的直到选到符合题目条件的选项为止。如果都不符合的话，就会再回溯到上一步，然后进入再进行新的选择，就这样重复选择，直到到达最终的状态。
1.3
通常回溯法算法适合用递归实现代码，当我们到达某一个节点时，尝试所有可能的选项并在满足条件的前提下递归地抵达下一个节点。

回溯法应用（实例化）
回溯法应用试题

题目:
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。

例如，在下面的3*4的矩阵中包含一条字符串“"bfce”的路径(路径中的字母用下画线标出)。但矩阵中不包含字符串“abfb”的路径，因为字符串的第一个字符b占据了矩阵中的第弟个格子之后，路径不能再次进入这个格子。

分析回溯法解决问题过程

第一行第二个字母‘b’和路径‘bfce’的第一个字符相等，所以从b开始分析，b有3种选择，向左到达字符a,向右到达字符t，向下到达字符f。

如果假如第一次向左走，会到达a，但是a不是路径中的第二个字符，所以会回溯到b，再次重新选择，直到有一次到达f才会继续向下走

在结点f也有3种选择，如果我们选择了向左到达字符c，但是之后再从左边的字符c走后，发现无论怎么走，都不可能到达字符c，所以只能向回回溯到达字符f再重新选择。一直类推，直到组成字符串bfce。

思路：

首先，在矩阵中任选一个格子作为路径的起点。假设矩阵中某个格子的字符为ch, 并且这个格子将对应于路径上的第i个字符。

如果路径上的第i个字符不是ch，那么这个格子不可能处在路径上的第i个位置。

如果路径上的第i个字符正好是ch，那么到相邻的格子寻找路径上的第i+1个字符。

除矩阵边界上的格子之外，其他格子都有4个相邻的格子。重复这个步骤，直到路径上所有字符都在矩阵中找到相应的位置。

由于回溯法的递归特性，路径可以看成一个栈，当在矩阵中定位了路径中前n个字符的位置之后，在与第n个字符对应的格子的周围都没有找到第n+1个字符，这时候只好在路径上回到第n-1个字符，重新定位第n个字符。

由于路径不能重复进入矩阵的格子，所以还需要定义和字符矩阵大小一样的布尔值矩阵，用来标识路径是否已经进入到每个格子。

当矩阵中坐标为(row,col)的格子和路径字符串中下标为pathLength的字符一样时，从4个相邻的格子(row,col-1)、(row-l,col)(row col+1)和(row+1,col)中去定位路径字符串中下标为pathLengh+1的字符。

如果4个相邻的格子都没有匹配字符串中下标为pathLengh+1的字符，则表明当前路径字符串中下标为pathLengh的字符在矩阵中的定位不正确，我们需要回到前一个字符(pathLengh-1)，然后重新定位。

一直重复这个过程，直到路径字符串上的所有字符都在矩阵中找到合适的位置(此时str[pathLength]==‘\0’)。