[数据结构与算法]回溯-机器人的运动范围-JZ66

描述
地上有一个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。请问该机器人能够达到多少个格子？

范围:
1 <= rows, cols<= 100
0 <= threshold <= 20

示例1

输入： 1,2,3
返回值： 3

示例2

输入： 0,1,3
返回值： 1

示例3

输入： 10,1,100
返回值： 29
说明：
[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]等等是无法到达的

思路：
这道题是典型的dfs（深度优先搜索）或者bfs（广度优先搜索）的算法，主要难点是在于判断条件的分析和机器人如何走。
根据题意，机器人从左上角开始移动，所以只需要计算 当前位置+右侧位置 + 下方位置，三点符合条件的数量，以此类推。
如果开局位置不确定，就需要计算当前位置+上下左右 五个位置符合条件的数量

时间复杂度：O(mn)， m,n为矩阵大小，每个元素最多访问过一次
空间复杂度：O(mn)
dfs模板：

dfs(){

    // 第一步，检查下标

    // 第二步：检查是否被访问过，或者是否满足当前匹配条件

    // 第三步：检查是否满足返回结果条件

    // 第四步：都没有返回，说明应该进行下一步递归
    // 标记
    dfs(下一次)
    // 回溯
}  
int main() {
    dfs(0, 0);
}

对应代码

public class Solution {
     
    public int movingCount(int threshold, int rows, int cols) {
        if(threshold < 0 || threshold > 20 
           || rows < 0 || rows > 100
           || cols < 0 || cols > 100) {
            return 0;
        }
        int [][] arr = new int [rows][cols];
        return dfs(0, 0, threshold, rows, cols, arr);
    }
    
    // 返回能够到达的格子数
    private int dfs(int x, int y, int threshold, int rows, int cols, int [][] arr) {
        //坐标超出界限或者已经访问过  直接返回0
        if (x >= rows || y >= cols || arr[x][y] == 1) {
            return 0;
        }
        //判断当前位置是否符合条件
        if (sum(x, y) > threshold) {
            return 0;
        }
        arr[x][y] = 1;
        //当前结果+右边格子+下面格子
        return 1 + dfs(x, y+1, threshold, rows, cols, arr)
            + dfs(x+1, y, threshold, rows, cols, arr);
    }
    //行坐标和列坐标的数位之和
    private int sum(int x, int y) {
        int sum = 0;
        while (x != 0) {
            sum += x % 10;
            x = x / 10;
        }
        while (y != 0) {
            sum += y % 10;
            y = y / 10;
        }
        return sum;
    }
}