剑指offer第六十六题。

题目描述

地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？

解题思路

基本的思路是同上一题的，就不再赘述思路了。至此，《剑指offer》66题全部刷完，这是我第三遍刷了，很多答案进行了优化，总体上是把比较好的方案总结在这上面，而不是只贪图简单而采取暴力解法，那样达不到真正的目的。下面的刷题主要是围绕牛客网的《leetcode在线编程训练》进行练习，后面的刷题进度可能总体较慢。

我的答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public class Solution {
    public int movingCount(int threshold, int rows, int cols)
    {
        //根据m行n列的方格，构造一个数组来标识是否已经判断过，已经判断过的话置为true，否则置为false
        //这里初始化默认是false
        boolean[][] flag = new boolean[rows][cols];
        //下面开始走，边走边判断周围是否符合
        //judge(初始横坐标i，初始横坐标j，行数，列数，k值，标识是否走过)
        return judge(0,0,rows,cols,threshold,flag);
    }
     
    private int judge(int i,int j,int rows,int cols,int threshold,boolean[][] flag){
        //越界、flsg=true说明已经走过，就不要再走了、行坐标和列坐标的数位之和大于k也跳过
        if(i<0 || j<0 || i>=rows || j>=cols || flag[i][j]==true || getK(i)+getK(j)>threshold)
            return 0;
        //机器人从[0,0]出发，必定是满足的，先置为true,所以要先加个1
        flag[i][j] = true;
        //基于回溯的思想，就是到达一个格子后，不断地判断他的周围四个格子是否满足要求，递归判断下去，必定走遍所有格子
        return judge(i-1,j,rows,cols,threshold,flag)+
                judge(i,j-1,rows,cols,threshold,flag)+
                judge(i+1,j,rows,cols,threshold,flag)+
                judge(i,j+1,rows,cols,threshold,flag)+1;
    }
   //计算数字每一位之和
    private int getK(int num){
        int sum = 0;
        do{
            sum += num%10;
        }while((num=num/10) > 0);
        return sum;
    }
}