一、题目描述
地上有一个 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。
请问该机器人能够到达多少个格子？
示例 1：
输入：m = 2, n = 3, k = 1
输出：3
示例 2：
输入：m = 3, n = 1, k = 0
输出：1
提示：
1 <= n,m <= 1000 <= k <= 20
二、题目解析
我们需要统计能走多少个格子，不能少统计也不能重复统计。
- 避免少统计：遍历所有能移动的格子
- 避免重复统计：每次统计完一个格子，将其移除
由于机器人是从左上角(0,0) 开始移动，所以移动方向必然是 下方 或者 右方，即机器人从格子的 左方 或者 上方 进入格子，从格子的 下方 或者 右方 离开格子。
接下来依次观察一下随着 k 的变大，符合要求的区域是哪些。
注：符合要求的区域并不代表机器人一定能够到达，因为中间有一些不符合要求的区域，机器人无法跨越。
当 k = 0 时:
当 k = 1 时:
当 k = 2 时:
当 k = 3 时:
当 k = 4 时:
我们以 k = 4 为例，演示机器人的移动。
当机器人移动到 4 这个格子的时候，无法再向下移动，因为下方的 5 超过了 4，属于无法进入的区域，根据我们之前的结论，机器人需要向右移动，此时右方的 5 也超过了 4，机器人无法再移动到任何一个新的格子，需要返回，左方是边界，因此只能向上返回，在返回的同时需要携带统计到的格子，避免遗失。
为了方便演示，在每个格子的四周分别设置一个小方块，表示机器人由此格子出发可到达区域的数量，实际上，我们只需要观察格子的下方和右方统计数即可，因为机器人只能此格子的 下方 或者 右方 离开格子，返回时也必然从此格子的 下方 或者 右方 返回到此格子并带来了统计的数量。
机器人从 4 返回 3 的同时，携带着统计的数量 1，记录在格子 3 的下方，表明机器人由 3 这个格子出发可到达区域的数量为 1，同时，为了避免多次统计格子 4，将格子 4 的状态清除。
接下来，让机器人从格子 3 的右方开始出发，探索右方可到达的区域。
到达格子 4 后，下方和右方都不可到达，返回并携带数量，同时清除状态。
接下来，机器人不断的重复从一个格子出发探索、返回携带数量、清除区域的操作。
最终统计出，当 k = 4 的时候，机器人可移动到达的格子数量为 15 。
机器人先从一个方向出发，直到到达不可到达的区域时才返回，符合 深度优先遍历 的性质。
机器人不断的重复从一个格子出发探索、返回携带数量、清除区域的操作，符合 递归 的性质。
所以，我们可以使用一个数组用来记录符合要求的格子是否被机器人访问过，若没有访问过，则在机器人返回的过程中将结果 + 1。
为了帮助你更好的理解整个过程，我特意做了一组动画，点开可以查看：
三、参考代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
class Solution {
public int movingCount(int m, int n, int k) {
// 使用临时变量 visited 记录格子是否被访问过
boolean[][] visited = new boolean[m][n];
// 开始深度优先遍历
return dfs(0, 0, m, n, k, visited);
}
public int dfs(int i, int j, int m, int n, int k, boolean[][] visited) {
// 行列索引越界
if( i >= m || j >= n ) return 0;
// 数位和超出目标值 k ，即不满足行坐标和列坐标的数位之和小于 k 的格子
if( k < sum( i , j ) ) return 0;
// 已经被访问过的重复格子
if ( visited[i][j] ) return 0;
//机器人进入了一个新格子，标注这个格子被访问过
visited[i][j] = true;
//沿着当前格子的右边和下边继续访问
return 1 + dfs( i + 1, j , m , n , k , visited ) + dfs( i , j + 1, m , n , k , visited);
}
//计算两个坐标数字的和
private int sum(int i, int j) {
int sum = 0;
while (i != 0) {
// 通过求余和取整的操作来计算
sum += i % 10;
i /= 10;
}
while (j != 0) {
sum += j % 10;
j /= 10;
}
return sum;
}
}
