剑指offer的机器人运动范围问题
//本人菜鸟,遇到了问题,请有空的大佬帮忙解惑?在此先谢谢各位大佬。代码中有我的疑惑。
题目描述
地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动,
每一次只能向左,右,上,下四个方向移动一格,
但是不能进入行坐标和列坐标的数位之和大于k的格子。
例如,当k为18时,机器人能够进入方格(35,37),因为3+5+3+7 = 18。
但是,它不能进入方格(35,38),因为3+5+3+8 = 19。请问该机器人能够达到多少个格子?
public class Solution {
public int movingCount(int threshold, int rows, int cols)
{
}
} public class Solution {
//向右和向下移动准备的数组
private static final int[][] next={{1,0},{0,1}};
private int rows; private int cols;
//用来记录机器人可走方格的个数
private static int temp=0;
public int movingCount(int threshold, int rows, int cols){
if(rows<0||cols<0){
return 0;
}
this.rows=rows;
this.cols=cols;
boolean[][] choose=new boolean[rows][cols];
int[][] matrix=new int[rows][cols];
move(threshold,0,0,matrix,choose);
// int sum=0;
// for(int i=0;i<rows;i++){
// for(int j=0;j<cols;j++){
// //计算机器人走过的方格个数
// if(choose[i][j]==true){
// sum++;
// }
// }
// }
// return sum;
return temp;
}
/**
* @param r 当前所在的行
* @param c 当前所在的列
* @param choose[][] 记录机器人走过的方格,走过记为true,走不到的记为false
*/
private void move(int threshold,int r,int c,int[][] matrix,boolean[][] choose){
if(r<0||r>=rows||c<0||c>=cols||choose[r][c]){
return;
}
if(panduan(threshold,r,c)){
choose[r][c]=true;
//temp值用来记录机器人可以走的方格的个数,每次有方格可以走,
//choose[r][c]设置为true,temp自增一次记录方格数
//但是答案就只有12%的正确率
//如果用注释掉的循环计算,答案100%通过
//不知道为什么用temp++就不行,用计算choose矩阵true的个数就可以
//求有空的大佬们帮忙解惑一下
temp++;
for(int[] n:next){
move(threshold,r+n[0],c+n[1],matrix,choose);
}
}
}
/**
* 计算行和列的各个位数的和是否超过给定值
*/
private boolean panduan(int threshold, int rows, int cols){
int sum1=0;
int sum2=0;
String str1=rows+"";
String str2=cols+"";
for(int i=0;i<str1.length();i++){
String ch1=str1.charAt(i)+"";
sum1+=Integer.parseInt(ch1);
}
for(int j=0;j<str2.length();j++){
String ch2=str2.charAt(j)+"";
sum2+=Integer.parseInt(ch2);
}
if(sum1+sum2<=threshold){
return true;
}else{
return false;
}
}
}
#笔试题目##Java##题解##面经##笔经##内推##悬赏#
