题解 | #机器人的运动范围

public class Solution {
    
    public int threshold;
    public int rows;
    public int cols;
    
    public int movingCount(int threshold, int rows, int cols) {
        // 初始化
        this.threshold = threshold;
        this.rows = rows;
        this.cols = cols;

        int[][] matrix = new int[rows][cols]; // 定义一个整型数组，用于存放哪些位置可达    0: 表示当前位置不可达    1: 表示当前位置可达
        int[][] sign = new int[rows][cols]; // 定义一个整型数组，用于存放哪些位置已经访问过    0: 未访问过    1: 访问过
        process(matrix, 0, 0, sign);
        
        int res = 0; // 定义一个整型变量，用于存放最终的返回结果
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (matrix[i][j] == 1) {
                    res++;
                }
            }
        }
        return res;
    }
    
    public void process(int[][] matrix, int x, int y, int[][] sign) {
        if (x < 0 || x >= rows || y < 0 || y >= cols || sign[x][y] == 1) { // 如果越界或者当前位置已经访问过，直接返回
            return;
        }
        sign[x][y] = 1; // 记录当前位置访问过
        if (!isValid(x, y)) { // 判断当前位置是否可达
            return; // 如果不可达，直接返回
        }
        matrix[x][y] = 1; // 如果可达，记录当前位置
        // 同时访问当前位置的上下左右
        process(matrix, x - 1, y, sign);
        process(matrix, x + 1, y, sign);
        process(matrix, x, y - 1, sign);
        process(matrix, x, y + 1, sign);
        sign[x][y] = 0; // 别忘了进行回溯
    }
    
    // 判断当前位置的坐标位数和是否小于 threshold
    public boolean isValid(int x, int y) {
        StringBuffer sb = new StringBuffer("");
        sb.append(x);
        sb.append(y);
        int num = 0;
        for (int i = 0; i < sb.length(); i++) {
            num += Integer.valueOf(sb.charAt(i) + "");
        }
        if (num <= threshold) {
            return true;
        }
        else {
            return false;
        }
    }
}