剑指offer(C++)-JZ13：机器人的运动范围(算法-回溯)-Toy模板网

这篇具有很好参考价值的文章主要介绍了剑指offer(C++)-JZ13：机器人的运动范围(算法-回溯)。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

作者：翟天保Steven
版权声明：著作权归作者所有，商业转载请联系作者获得授权，非商业转载请注明出处

剑指offer(C++)-JZ13：机器人的运动范围(算法-回溯),剑指offer,算法,c++,矩阵

题目描述：

地上有一个 rows 行和 cols 列的方格。坐标从 [0,0] 到 [rows-1,cols-1] 。一个机器人从坐标 [0,0] 的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于 threshold 的格子。例如，当 threshold 为 18 时，机器人能够进入方格 [35,37] ，因为 3+5+3+7 = 18。但是，它不能进入方格 [35,38] ，因为 3+5+3+8 = 19 。请问该机器人能够达到多少个格子？

数据范围： 0≤threshold≤15 ，1≤rows,cols≤100

进阶：空间复杂度O(nm) ，时间复杂度O(nm)

示例：

输入：

10,1,100

返回值：

说明：

[0,0],[0,1],[0,2],[0,3],[0,4],[0,5],[0,6],[0,7],[0,8],[0,9],[0,10],[0,11],[0,12],[0,13],[0,14],[0,15],[0,16],[0,17],[0,18],[0,19],[0,20],[0,21],[0,22],[0,23],[0,24],[0,25],[0,26],[0,27],[0,28] 这29种，后面的[0,29],[0,30]以及[0,31]等等是无法到达的

解题思路：

本题是回溯法的经典题目，也常用于解决迷宫问题。思路如下：文章来源地址https://www.toymoban.com/news/detail-525474.html

用flags记录当前点是否走过，用decompose函数分解出行列数对应的数字，来和阈值比对，以判断道路是否可通。
解题代码本质上还是用的递归回溯法和深度优先遍历。
moving函数从起点出发，每走到一个位置，就向其四个方向分别继续前行，可以分出许多支路。每个支路直到某个位置堵死就停下，再一层层回溯，最后即可得到结果。注意前行过程中对flags进行实时更新，避免重复踩格子。

测试代码：

class Solution {
public:
    // 移动计数
    int movingCount(int threshold, int rows, int cols) {
        if(rows <= 0 || cols <= 0 || threshold < 0)
            return 0;
        // 记录位置是否被走过
        vector<vector<bool>> flags(rows, vector<bool>(cols, false));
        // 起点出发，递归回溯
        int count = moving(threshold, rows, cols, 0, 0, flags);
        return count;
    }

    // 移动
    int moving(int threshold, int rows, int cols, int row, int col, vector<vector<bool>>& flags){
        if(row < 0 || col < 0 || row >= rows || col >= cols || flags[row][col]
           || decompose(row) + decompose(col) > threshold )
            return 0;
        // 此点通
        flags[row][col] = true;
        // 四向移动
        return 1 + moving(threshold, rows, cols, row - 1, col, flags) 
                 + moving(threshold, rows, cols, row + 1, col, flags)
                 + moving(threshold, rows, cols, row, col - 1, flags)
                 + moving(threshold, rows, cols, row, col + 1, flags);
    }

    // 数字分解
    int decompose(int num){
        int sum = 0;
        while(num > 0){
            sum += num % 10;
            num /= 10;
        }
        return sum;
    }
};

到了这里，关于剑指offer(C++)-JZ13：机器人的运动范围(算法-回溯)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！