【回溯法】机器人的移动范围

1. 概念引入^[1]

回溯法（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

2. 基本思想^[2]

在回溯法中，每次扩大当前部分解时，都面临一个可选的状态集合，新的部分解就通过在该集合中选择构造而成。这样的状态集合，其结构是一棵多叉树，每个树结点代表一个可能的部分解，它的儿子是在它的基础上生成的其他部分解。树根为初始状态，这样的状态集合称为状态空间树。
回溯法对任一解的生成，一般都采用逐步扩大解的方式。每前进一步，都试图在当前部分解的基础上扩大该部分解。它在问题的状态空间树中，从开始结点（根结点）出发，以深度优先搜索整个状态空间。这个开始结点成为活结点，同时也成为当前的扩展结点。在当前扩展结点处，搜索向纵深方向移至一个新结点。这个新结点成为新的活结点，并成为当前扩展结点。如果在当前扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。此时，应往回移动（回溯）至最近的活结点处，并使这个活结点成为当前扩展结点。回溯法以这种工作方式递归地在状态空间中搜索，直到找到所要求的解或解空间中已无活结点时为止。

3. 回溯法解题的关键要素^[3]

确定了问题的解空间结构后，回溯法将从开始结点(根结点)出发，以深度优先的方式搜索整个解空间。开始结点成为活结点，同时也成为扩展结点。在当前的扩展结点处，向纵深方向搜索并移至一个新结点，这个新结点就成为一个新的活结点，并成为当前的扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前的扩展结点就成为死结点。此时应往回移动(回溯)至最近的一个活结点处，并使其成为当前的扩展结点。回溯法以上述工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已无活结点时为止。
运用回溯法解题的关键要素有以下三点：
(1) 针对给定的问题，定义问题的解空间；
(2) 确定易于搜索的解空间结构；
(3) 以深度优先方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索。

4. 应用实例

1. 问题描述
地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？
1. 问题分析
首先，这不是一个求路径的问题，而是求运动范围。使用递归，使用一个bool值矩阵记录机器人能否进入某个格子。让机器人从[0,0]开始移动，当它进入一个格子(i,j)时，判断机器人能否进入这个格子（是否在方格里，是否已经访问过，坐标数位和是否大于k），如果能进入如果机器人能进入(i,j)的格子就接着判断它能否进入四个相邻的格子(i,j-1),(i,j+1),(i-1,j),(i+1,j)，如果不能进入就返回上一个格子，重复上述行为，直到走完所有有效范围。
1. 代码表示

#include <iostream>

using namespace std;

//求坐标数位之和
int getDigitSum(int i,int j){
    int sum=0;
    while(i){
        sum+=i%10;
        i=i/10;
    }
    while(j){
        sum+=j%10;
        j=j/10;
    }
    return sum;
}

//计算从某个点出发能到大的格子个数
//threshold为机器人能的格子的数位之和的阈值，rows总行数，cols为总列数，i为格子横坐标，j为格子纵坐标，visited为记录机器人能否进入某个格子的bool值矩阵，true为可以进入，false为不能进入
int getMovingCount(int threshold, int rows, int cols, int i, int j, bool *visited)
{
    //count代表能到达的格子数，移动之前初始值为0
    int count = 0;

    //坐标数位和是否大于阈值，或不在方格里，或已经访问过，机器人不能进入该格子
    if((threshold < getDigitSum(i, j))||(i >= rows)||(j >= cols)||(i < 0)||(j < 0)||(visited[i*cols+j]))
        return 0;

    //满足所有访问条件，说明机器人可以进入该格子，bool矩阵对应位置置位值改为true
    visited[i*cols+j] = true;

    //使用回溯法，检查当前格子四周的格子是否满足条件，并更新count值记录格子个数
    count = 1 + getMovingCount(threshold, rows, cols, i+1, j, visited)
              +getMovingCount(threshold, rows, cols, i, j+1, visited)
              +getMovingCount(threshold, rows, cols, i-1, j, visited)
              +getMovingCount(threshold, rows, cols, i, j-1, visited);

    return count;
}

//给定一个方格和一个阈值，以坐标（0，0）为起点移动
int movingCount(int threshold, int rows, int cols){

    //输入错误参数，即阈值过小或行列小于等于0的情况
    if((threshold < 0)||(rows <=0)||(cols <= 0))
        return 0;
    
    bool *visited = (bool *)malloc(rows*cols);  //初始化一个bool值矩阵
    memset(visited,false,rows*cols);   //分配内存空间，把矩阵的初始元素值都设为false

    int count = getMovingCount(threshold,rows,cols,0,0,visited);
    free(visited);  //释放
    return count;   //返回结果
}  

int main() {
    cout << movingCount(4, 23, 1)<< endl;
    return 0;
}

感谢阅读，如有问题欢迎指正！

[1][2][3] 引用自百度百科

【回溯法】机器人的移动范围

1. 概念引入[1]

2. 基本思想[2]

3. 回溯法解题的关键要素[3]

4. 应用实例

1. 概念引入^[1]

2. 基本思想^[2]

3. 回溯法解题的关键要素^[3]