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

这道题乍看很难，仔细一想发现很简单，只用到了递归，没有用到回溯 空间复杂度O（mn）创建了一个used数组来记录访问过的格子 时间复杂度（4mn）每个格子经历4次递归

public class Solution { boolean[][] used; int count = 0; public int movingCount(int threshold, int rows, int cols) {

   used = new boolean[rows][cols];
    backTracking(threshold,0,0);
    return count;
    
}

public void backTracking(int threshold,int row,int col){
	//这里判断索引是否合法
    if(row < 0 || col < 0 || row >= used.length || col >= used[0].length){
        return;
    }
    //判断索引是否满足threshold
    if(isSum(row,col) > threshold){
        return;
    }
    //Boolean数组默认值为false，如果为false，说明这个格子没有访问过，count++
    if(used[row][col] == false){
        count++;
    }else{
        return;
    }
    //将已访问的格子标记为true，即已访问过
    used[row][col] = true;
    //递归访问上下左右的格子
    backTracking(threshold,row + 1,col);
    backTracking(threshold,row - 1,col);
    backTracking(threshold,row, col + 1);
    backTracking(threshold,row , col - 1);

    return;       
    
}
public int isSum(int row,int col){
    int sum = 0;
    while(row != 0){
        sum += row % 10;
        row = row / 10;
    }
    while(col != 0){
        sum += col % 10;
        col = col / 10;            
    }
    return sum;
}

}