题目描述

地上有一个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
输入：1,2,3
返回值：3

题目分析

对于计算该机器人能够到达多少格子，首先可以采取暴力的遍历方法，遍历所有的格子，计算能够满足条件的格子数。
这里判断的条件是坐标的数位和要小于要求的数，同时因为是暴力遍历，需要判断这个位置是否能由之前的位置到达。
计算数位和的代码如下，主要是统计数字的每位数之和。

int get(int x) {
     int res = 0;
     while (x != 0) {
        res += x % 10;
        x /= 10;
     }
     return res;
}

解题思路

方法1：暴力法，直接遍历数组
为了判断是否能够达到某个位置的格子，定义一个与格子大小一样的访问数组visited[n][m]，只有在满足它的上下左右是否已经有格子到达的，才能在满足条件。
访问的双循环，在循环内，判断的条件有：
①坐标和是否满足条件
②坐标的左边或上边是否可达（因为坐标和的大小计算，可以排除右边或下边的位置（一定比当前位置大））
如图：参数（3,3,2）
图片说明

方法2：回溯法（DFS）
关于数组的遍历问题，可以使用深度遍历，即从初始位置开始一直朝某个方向一直判断，直到不满足条件则回退，去其他方向判断，直到所有方向都判断完成后，可以计算总共可以到达的格子数。
回溯法相比暴力法，不一定要遍历整个数组，碰到不满足的条件的可以排除。
在回溯法中，也需要使用标记数组 visited[][]，来判断当前位置是否被访问过。
如图，先按照从右方向递归，再转到向下（之后又是右），重复之前的步骤，直到所有可达的格子遍历完。
图片说明

代码实现

方法1：暴力法，直接遍历数组

public int movingCount(int threshold, int rows, int cols) {
        if (threshold == 0) {
            return 1;
        }
        // 标记数组
        boolean[][] vis = new boolean[rows][cols];
        // 起始坐标默认已经包括
        int ans = 1;
        vis[0][0] = true;
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                // 直接遍历整个数组
                if ((i == 0 && j == 0) || get(i) + get(j) > threshold) {
                    continue;
                }
                // 边界判断，判断是否能从左边过来
                if (i - 1 >= 0) {
                    vis[i][j] |= vis[i - 1][j];
                }
                // 边界判断，判断是否能从上边过来
                if (j - 1 >= 0) {
                    vis[i][j] |= vis[i][j - 1];
                }
                // 位置可以到达，则数量加1
                ans += vis[i][j] ? 1 : 0;
            }
        }
        return ans;
    }
   // 计算数位和
    private int get(int x) {
        int res = 0;
        while (x != 0) {
            res += x % 10;
            x /= 10;
        }
        return res;
    }

时间复杂度：O(nm)，n是rows排数，m是cols列数，需要遍历整个数组；
空间复杂度：O(nm)，需要消耗n*m空间的标记数组；

方法2：回溯法（DFS）

    // 使用静态变量作为结果返回
    public static int num = 0;
    public int movingCount(int threshold, int rows, int cols) {
        // 标志变量数组，标记位置是否访问
        boolean[][] visited = new boolean[rows][cols];
        movingCount(threshold, rows, cols, 0, 0, visited);
        return num;
    }

    public void movingCount(int threshold, int rows, int cols, int i, int j, boolean[][] visited){
        //当坐标非法时排除；当坐标已访问过排除；坐标和不满足时排除
        if(i<0 || i>=rows || j<0 || j >= cols || visited[i][j] || check(i,j,threshold)){
            return ;
        }
        // 剩下的即为满足的情况，数量加1，标记访问过
        num++;
        visited[i][j] = true;
        // 继续访问该坐标的右、下位置
        movingCount(threshold, rows, cols, i+1, j, visited);
        movingCount(threshold, rows, cols, i, j+1, visited);


    }
    // 判断坐标和是否满足条件
    public boolean check(int i, int j, int threshold){
        int sum = count(i) + count(j);
        return sum > threshold;
    }
    // 计算数位和
    public int count(int n){
        int res = 0;
        while(n != 0){
            res += n % 10;
            n /= 10;
        }
        return res;
    }

时间复杂度：O(nm)，n是rows排数，m是cols列数，递归需要将数组中所有满足的情况遍历一遍，最差情况遍历整个数组；
空间复杂度：O(nm)，需要消耗n*m空间的标记数组；