Question13.java

package question;

/**
 * 机器人的运动范围
 * 地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，
 * 但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。
 * 但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？
 *
 * @author ahscuml
 * @date 2018/9/12
 * @time 10:20
 */
public class Question13 {
    private static int count = 0;

    /**
     * 测试用例
     */
    public static void main(String[] args) {
        int threshold = 3;
        int rows = 4, cols = 4;
        System.out.println(movingCount(threshold,rows,cols));
    }

    public static int movingCount(int threshold, int rows, int cols) {
        // 验证输入的有效性
        if (threshold <= 0 || rows <= 0 || cols <= 0) {
            return 0;
        }
        // 记录是否走过的数组
        boolean[][] flag = new boolean[rows][cols];
        return canReach(threshold, 0, 0, rows, cols, flag);
    }

    private static int canReach(int threshold, int i, int j, int rows, int cols, boolean[][] flag) {
        // 递归终止条件
        if (i >= rows || j >= cols || i < 0 || j < 0 || numSum(i) + numSum(j) > threshold || flag[i][j] == true) {
            return 0;
        }
        flag[i][j] = true;
        return canReach(threshold, i + 1, j, rows, cols, flag) + canReach(threshold, i - 1, j, rows, cols, flag) +
                canReach(threshold, i, j + 1, rows, cols, flag) + canReach(threshold, i, j - 1, rows, cols, flag) + 1;
    }

    private static int numSum(int i) {
        int sum = 0;
        do {
            sum += i % 10;
        } while ((i = i / 10) > 0);
        return sum;
    }
}