中等难度的高级测试开发岗算法题：机器人的运动范围
共 361字，需浏览 1分钟
·
2020-08-14 18:04
题目信息：
地上有一个m行n列的坐标方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入坐标方格 [35, 37] ，因为3+5+3+7=18 <= k。但它不能进入方格 [35, 38]，因为3+5+3+8=19 > k。请问该机器人能够到达多少个格子？
示例 1：
输入：m = 2, n = 3, k = 1
输出：3
示例 2：
输入：m = 3, n = 1, k = 0
输出：1
提示：1 <= n,m <= 100; 0 <= k <= 20
解题思路：
这是一道中等难度的算法题，可能出现在高级测试开发等面试场景中。这题是对空间搜索和动态规划等算法点的考察，了解这个出题点后，我们就可以针对性的编码实现了。
1、我们根据坐标的行列（m, n）值，画出一张mxn的矩阵，也就是一个[m][n]的二维数组，数组的下标即是坐标；2、对数组进行遍历，并判断当前坐标(x,y)是否满足：x和y的数位之和小于等于k；
如何计算位数之和？这里需要用到求余和除法，由于提示中告知k小于等于100，那么我们计算x坐标的位数和就只需要 (x/10) + (x%10)，但对于k=100的情况需要单独处理，k=100时，位数和=1。
3、对于符合条件的坐标，我们需要继续往上下左右四个方向进行搜索，指导遇到下面情况就退出搜索：
•超出边界•不符合位数和的条件•已经搜索过了，数组值为1
4、为了记录搜索的结果，我们可以将 [m][n]的二维数组设置成true和false或者0和1的值，符合条件就将数组值设置为1；5、最后我们再遍历一次数组，统计数组值为1的数量即得出最终的结果。
代码实现：
class Solution {public int movingCount(int m, int n, int k) {if (m < 1 || n < 1) {return 0;}if (k == 0) {return 1;}int counter = 0;int[][] arr = new int[m][n];for (int i = 0; i < m; i ++) {for (int j = 0; j < n; j++) {arr[i][j] = 0;}}dfs(arr, k, 0, 0);//从(0,0)开始搜索for (int i = 0; i < m; i ++) {for (int j = 0; j < n; j++) {if (arr[i][j] == 1) {counter++;}}}return counter;}private void dfs(int[][] arr, int k, int x, int y){int m = arr.length;int n = arr[0].length;if (x<0 || x>m-1 || y<0 || y >n-1 || arr[x][y] == 1) {return;}if (calc(x,y) <= k) {arr[x][y] = 1;dfs(arr,k, x+1,y);dfs(arr,k, x-1,y);dfs(arr,k, x,y-1);dfs(arr,k, x,y+1);}}private int calc(int i, int j) {int sum = 0;if (i == 100) {sum += 1;} else if (i >= 10) {sum += (i/10) + (i%10);} else {sum += i;}if (j == 100) {sum += 1;} else if (j >= 10) {sum += (j/10) + (j%10);} else {sum += j;}return sum;}}