回溯法思想（剑指Offer 65/66）
回溯法例子！！！
1
编程题
【剑指Offer】矩阵中的路径
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。例如 a b c e s f c s a d e e 矩阵中包含一条字符串"bccced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。
思路： 今天我们要来说一说回溯法的思想，其是一个十分通用的解法，并且其思路容易理解，代码的可读性较强，通过剪枝的方法可以提高其遍历的效率。但是，对于大数量级的数据，回溯法显然效率低，明明是错误的还是要进行搜索，直到列举出所有的解法！
虽然不是一个高明的方法，但思路简单，可以快速的解决很多问题！在回溯法中，流程如下：
void dfs(int 当前状态)
{
if(当前状态为边界状态)
{
记录或输出
return;
}
for(i=;i<n;i++) //横向遍历解答树所有子节点
{
//扩展出一个子状态。
修改了全局变量
if(子状态满足约束条件)
{
dfs(子状态)
}
恢复全局变量//回溯部分
}
}
最后我们来实战下吧，对于dfs而言，第一，首先要清楚递归函数如何退出，找出dfs函数的退出条件。第二，确定子状态，然后对每个子状态进行求解。由于题目中说，路径从矩阵中的任意一个格子开始，每一步可以有四个选择（向左，向右，向上，向下），这也就是我们的四个子状态！并且如果该路径经过了一个格子，则不能再次进入了。因此我们需要标记每个格子是否访问过，因此visited就相当于是全局变量，我们在递归开始对其进行修改，在递归结束后对其进行标记消除，也就是回溯部分！这就是我们通常正规的回溯算法！
解题代码：
class Solution {
public:
bool hasPath(char* matrix, int rows, int cols, char* str)
{
if(matrix == nullptr || rows < || cols < || str==nullptr)
return false; // 去除一些样例
bool * visited = new bool[rows*cols];
memset(visited, , rows*cols);
int pathLength = ;
for(int row = ;row < rows; ++row)
{
for(int col = ;col < cols; ++col)
{
if(str[] == matrix[row*cols+col] && hasPathCore(matrix, rows, cols, row, col, str, pathLength, visited))
{
return true;
}
}
}
delete [] visited;
return false;
}
bool hasPathCore(const char* matrix, int rows, int cols, int row, int col,
const char* str, int& pathLength, bool* visited)
{
if(str[pathLength] == '\0')
return true;
bool hasPath = false;
if(row >= && row < rows && col >= && col < cols &&
matrix[row*cols+col] == str[pathLength] && !visited[row*cols+col])
{
++pathLength; // 修改全局变量
visited[row*cols+col] = true;
hasPath = hasPathCore(matrix, rows, cols, row, col - , str, pathLength, visited)
|| hasPathCore(matrix, rows, cols, row - , col, str, pathLength, visited)
|| hasPathCore(matrix, rows, cols, row, col + , str, pathLength, visited)
|| hasPathCore(matrix, rows, cols, row + , col , str, pathLength, visited);
if(!hasPath)
{
--pathLength; // 恢复全局变量，回溯为原来状态
visited[row * cols + col] = false;
}
}
return hasPath;
}
};【剑指Offer】机器人的运动范围
地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？
思路： 趁热打铁，我们再来一道题目，也类似于上面的题目，只不过这道题目我们需要花很多心思来确定递归函数的结束条件：即每个格子能否被访问到！最关键的两个条件是，首先没有标记访问，其次是其坐标的数位之和等于k。如果全部满足，则当前状态等于以上所有子状态的解+1。
解题代码：
class Solution {
public:
int movingCount(int threshold, int rows, int cols)
{
if(threshold < || rows < || cols < )
return false;
bool * visited = new bool[rows*cols];
memset(visited, , rows*cols);
int count = movingCountCore(threshold, rows, cols, , , visited);
delete [] visited;
return count;
}
int movingCountCore(int threshold, int rows, int cols, int row, int col, bool* visited)
{
int count = ;
if(check(threshold, rows, cols, row, col, visited))
{
visited[row*cols+col] = true;
count = + movingCountCore(threshold, rows, cols, row + , col, visited)
+ movingCountCore(threshold, rows, cols, row - , col, visited)
+ movingCountCore(threshold, rows, cols, row, col + , visited)
+ movingCountCore(threshold, rows, cols, row, col - , visited);
}
return count;
}
bool check(int threshold, int rows, int cols, int row, int col, bool* visited)
{
if(row >= && row < rows && col >= && col < cols && !visited[row*cols+col] &&
getNum(row)+getNum(col) <= threshold)
return true;
return false;
}
int getNum(int number)
{
int sum = ;
while(number)
{
sum += number % ;
number /= ;
}
return sum;
}
};2
腾讯云开发者
