一、题目描述
地上有一个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 <= 100
0 <= k <= 20
二、思路讲解
对于我这种算法小白来说，看见在矩阵中上下左右跑的，直接无脑深搜。
从（0，0）开始，像上下左右方向分别找满足条件的节点，如果某一个方向满足条件，就走到这个位置，继续找这个位置的上下左右（递归）；如果某一个方向不满足条件，应该排除掉这个方向（剪枝操作）。当四个方向都找完之后，回到上一个节点（回溯）。
为了避免走“回头路”，避免将已经访问过的节点再算上去，我们定义一个二位数组visited，来标记是否访问过。
然后是确定跳出递归的条件：
1、超出边界；
2、数位之和大于k；
3、已经被访问过。
三、Java代码实现
class Solution { public int movingCount(int m, int n, int k) { //用来标记该位置是否访问过 为1则访问过 int [][]visited = new int[m][n]; return dfs(0, 0, m, n, k, 0, visited); } public static int dfs(int i, int j, int m, int n, int k, int count, int [][]visited) { //如果指针越界 或 行列数位之和大于k 或 被访问过，则直接返回count次数 if(i<0 || j<0 || i>=m || j>=n || fun(i, j)>k || visited[i][j]==1) { return count; } //将当前位置标记为已访问 visited[i][j] = 1; //满足条件的格子数+1 count++; count = dfs(i-1, j, m, n, k, count, visited); //往上找 count = dfs(i+1, j, m, n, k, count, visited); //往下找 count = dfs(i, j-1, m, n, k, count, visited); //往左找 count = dfs(i, j+1, m, n, k, count, visited); //往右找 return count; } //用来计算坐标为（m，n）的数位之和 public static int fun(int m, int n){ int sum = 0; while(m!=0){ sum = sum + m%10; m = m/10; } while(n!=0){ sum = sum + n%10; n = n/10; } return sum; } }
四、时空复杂度分析
时间复杂度： O(MN) 最坏情况下，机器人遍历整个矩阵
空间复杂度： O(MN) 最坏情况下，visited矩阵存储所有单元格的索引
五、代码优化
1、不需要向上和向左搜索
由于机器人从左上角出发，所以他只会往右或往下走，因此不需要向上和向左搜索。
2、 数位求和无需循环
由于题目中矩阵的坐标都是一位或者两位数，要想求这样数字的数位和只需要x%10 + x/10即可 。
3、函数传值还可简化
其实dfs中不需要把count传进去计算所有满足条件的格子数量，只需要返回这一支的满足条件的数量就行了。
class Solution { public int movingCount(int m, int n, int k) { //用来标记该位置是否访问过 为1则访问过 int [][]visited = new int[m][n]; return dfs(0, 0, m, n, k, visited); } public static int dfs(int i, int j, int m, int n, int k, int [][]visited) { //如果指针越界 或 行列数位之和大于k 或 被访问过，则直接返回count次数 if(i<0 || j<0 || i>=m || j>=n || fun(i, j)>k || visited[i][j]==1) { return 0; } //将当前位置标记为已访问 visited[i][j] = 1; // 往下找 往右找 return 1 + dfs(i+1, j, m, n, k, visited) + dfs(i, j+1, m, n, k, visited); } //用来计算坐标为（m，n）的数位之和 public static int fun(int m, int n){ return m%10 + m/10 + n%10 + n/10; } }
