推荐

完整《剑指Offer》算法题解析系列请点击 👉 《剑指Offer》全解析 Java 版

题目描述

地上有一个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)
    {
   
        
    }
}

思路： 递归回溯

和65题思路差不多：《剑指offer》—— 65. 矩阵中的路径（Java）

实现：

public class Solution {
   
    public int movingCount(int threshold, int rows, int cols)
    {
   
        //设置标记，初始化全都为 false， 走过的设置为true
        boolean flag[][] = new boolean[rows][cols];
        return check(0, 0, rows, cols, flag, threshold);
    }
    
    private int check(int i, int j, int rows, int cols, boolean[][] flag, int threshold) {
   
        //数组越界，坐标之和大于 threshold ，该坐标位置的格子已经走过了，
        if (i < 0 || i >= rows || j < 0 || j>= cols || numberSum(i) + numberSum(j) > threshold || flag[i][j] == true) {
   
            return 0;
        }
        //已经走过的格子设置为 true
        flag[i][j] = true;
        
        //递归检查上下左右的格子是否符合
        return check(i - 1, j, rows, cols, flag, threshold)
            + check(i + 1, j, rows, cols, flag, threshold)
            + check(i, j - 1, rows, cols, flag, threshold)
            + check(i, j + 1, rows, cols, flag, threshold)
            + 1;
    }
    
    //求坐标之和，注意，它是每位都算个位来相加。
    private int numberSum(int i) {
   
        int sum = 0;
        do {
   
            sum += i % 10;
        }while ((i = i / 10) > 0);
        
        return sum;
        
    }
    
}

看完之后，如果还有什么不懂的，可以在评论区留言，会及时回答更新。

这里是猿兄，为你分享程序员的世界。

非常感谢各位大佬们能看到这里，如果觉得文章还不错的话， 求点赞👍 求关注💗 求分享👬求评论📝 这些对猿兄来说真的 非常有用！！！

注： 如果猿兄这篇博客有任何错误和建议，欢迎大家留言，不胜感激！：**