剑指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##题解##面经##笔经##内推##悬赏#