题目描述

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

解题思路

• 回溯法，递归调用，从0节点开始出发，可以走上下左右四个位置，需要声明一个布尔矩阵表示当前对应的行列节点是否已经访问过。这个方法在图的检查中用的爱多了
• 每一次进入一个节点后首先检查这个节点是否可用，即是下标是否符合0<=row<rows, 0<=col<cols,该节点是否已经访问过，该节点的行列值的各位和是否超过要求的threshold，如果不满足以上条件返回一个0值
• 如果满足条件，那么此时需要将该节点状态置为true表示已经访问过，然后返回的是1+上+下+左+右的值，进行深层次递归即可

Java源代码

public class Solution {
    public int movingCount(int threshold, int rows, int cols)
    {
        if (rows<=0 || cols<=0||threshold<0) return 0;
        boolean[][] visited = new boolean[rows][cols];
        for (int i=0; i<rows; i++) {
            for (int j=0; j<cols; j++) {
                visited[i][j]=false;
            }
        }
        int result = movingCountCore(threshold, 0, 0, rows, cols, visited);
        return result;
    }
    
    private static int movingCountCore(int threshold, int row, int col,
                                       int rows, int cols, boolean[][] visited) {
        if (row<0||row>=rows||col<0||col>=cols||visited[row][col]) return 0;
        visited[row][col]=true;
        int sum = digitSum(row, col);
        if (sum > threshold) return 0;
        return 1+movingCountCore(threshold, row+1, col, rows, cols, visited)
            + movingCountCore(threshold, row-1, col, rows, cols, visited)
            + movingCountCore(threshold, row, col+1, rows, cols, visited)
            + movingCountCore(threshold, row, col-1, rows, cols, visited);
    }
    
    private static int digitSum(int a, int b) {
        int sum = 0;
        while (a!=0 || b!=0) {
            sum += a%10;
            a = a/10;
            sum += b%10;
            b = b/10;
        }
        return sum;
    }
}