剑指Offer(Java版)第十二题:地上有一个m行n列的方格。一个机器人从坐标(0, 0)的格子开始移动, 它每一次可以向左、右、上、下移动一格,但不能进入行坐标和列坐标的数位之和大于k的格子。 如,当k为18时,机器人能够进入方格(35, 37),因为3+5+3+7=18。但它不能进入方格(35, 38), 因为3+5+3+8=19。请问该机器人能够到达多少个格子?

/*地上有一个m行n列的方格。一个机器人从坐标(0, 0)的格子开始移动,
它每一次可以向左、右、上、下移动一格,但不能进入行坐标和列坐标的数位之和大于k的格子。
如,当k为18时,机器人能够进入方格(35, 37),因为3+5+3+7=18。但它不能进入方格(35, 38),
因为3+5+3+8=19。请问该机器人能够到达多少个格子?
*/
public class Class12 {
public int moveCount(int rows, int cols, int threshold){
boolean anchor[][] = new boolean[rows][cols];
return moveCountMain(0,0,rows,cols,anchor,threshold);
}
public int moveCountMain(int row, int col, int rows, int cols, boolean[][] anchor, int threshold){
if(row < 0 || row >= rows || col < 0 || col >= cols || countResult(row) + countResult(col) > threshold || anchor[row][col] == true){
return 0;
}
anchor[row][col] = true;
return moveCountMain(row,col-1,rows,cols,anchor,threshold)
+ moveCountMain(row,col+1,rows,cols,anchor,threshold)
+ moveCountMain(row + 1,col,rows,cols,anchor,threshold)
+ moveCountMain(row - 1,col,rows,cols,anchor,threshold) + 1;
}
public int countResult(int a){
int sum = 0;
while(a > 0){
sum += a % 10;
a = a / 10;
}
return sum;
}
public void test(int threshold, int rows, int cols, int expected){
if (moveCount(threshold, rows, cols) == expected)
System.out.println("Passed.");
else
System.out.println("Failed.");
}

public static void main(String[] args) {
// TODO Auto-generated method stub
Class12 c = new Class12();
c.test(15, 20, 20, 359);
}
}

剑指Offer(Java版)第十二题:地上有一个m行n列的方格。一个机器人从坐标(0, 0)的格子开始移动, 它每一次可以向左、右、上、下移动一格,但不能进入行坐标和列坐标的数位之和大于k的格子。 如,当k为18时,机器人能够进入方格(35, 37),因为3+5+3+7=18。但它不能进入方格(35, 38), 因为3+5+3+8=19。请问该机器人能够到达多少个格子?

上一篇:android studio打包weexplus项目常见错误


下一篇:使用存储即服务优化混合云平台