中等难度的高级测试开发岗算法题:机器人的运动范围
题目信息:
地上有一个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;
}
}