一、题目
地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格[35, 37]，因为3 5 3 7=18。但它不能进入方格 [35, 38]，因为3 5 3 8=19。请问该机器人能够到达多少个格子？
二、示例
2.1> 示例 1：
【输入】m = 2, n = 3, k = 1 【输出】3
2.2> 示例 2：
【输入】m = 3, n = 1, k = 0 【输出】1
提示：
- •
1<= n,m <=100 - •
0<= k <=20
三、解题思路
根据题目描述，我们需要在m行n列的矩阵中寻找行坐标和列坐标的数位之和不大于k的格子数量。那么我们需要做到如下几个步骤：
【步骤1】提供计算
行坐标和列坐标数位之和的函数方法。 【步骤2】执行深度优先算法或广度优先算法，对比每个盒子数位之和是否满足不大于k。 【步骤3】我们要采用某种方式，可以防止重复遍历。
确定了具体的解题步骤，我们首先来看如何计算一个数字的数位之和。常用的方式是，通过与10取余（）的方式来获得最后一位的数字，那么获取到个位之后，再通过与10取整（/10）的方式来移除最后一位，那么再次通过与10取余计算后，就取得了原数字的十位数字了，依次类推，直至所有数字的位数都截取出来。并且在每次获取最后一位的操作过程中，都进行加合计算，最终的结果就是某个数字的数位之和了。具体操作，如下图所示：
那么上面我们解决了步骤1的函数算法，下面我们选取深度优先来对矩阵中的每个格子执行遍历操作。在遍历过程中，由于我们是从[0,0]这个格子开始遍历的，它是所有格子数位合的最小值（即：0 0=0），那么对于深度遍历的方向来说，我们不需要考虑会使整个数位和变小的情况，即：向上遍历（row-1）和向左遍历（col-1），只需要考虑向下遍历（row 1）和向右遍历（col 1）这两种行走路径。那么，我们再整理一下如下几个结束路径的条件：
【路径结束条件1】row >= m 或者 col >= n； 【路径结束条件2】格子数位之和大于k； 【路径结束条件3】待行走的格子已经被走过了。
针对“路径结束条件3”，我们可以采用二维数组或者哈希表的方式，记录走过的格子即可。下面是以输入：m = 4, n = 6, k = 5为例，具体演示了处理流程。请见下图所示：
四、代码实现
代码语言：javascript复制class Solution {
boolean[][] mark;
public int movingCount(int m, int n, int k) {
mark = new boolean[m][n];
return dfs(0, 0, m, n, k);
}
int dfs(int row, int col, int m, int n, int k) {
if (row >= m || col >= n || mark[row][col] || sum(row) sum(col) > k) return 0;
mark[row][col] = true;
return 1 dfs(row 1, col, m, n, k) dfs(row, col 1, m, n, k);
}
int sum(int x) {
int s = 0;
while(x != 0) {
s = x % 10;
x = x / 10;
}
return s;
}
}
