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

拆解问题，使用回溯法

先实现canReach方法，再从[0][0]出发，对每个节点判断是否可达，若可达，在判断其上下左右节点是否可达。

其中 “对每个节点判断是否可达，若可达，在判断其上下左右节点是否可达。” 可以使用递归实现。

public class Solution {
    public int movingCount(int threshold, int rows, int cols) {
        
        if(threshold < 0 || rows == 0 || cols == 0){
            return 0;
        }
        
        
        boolean[][] visited = new boolean[rows][cols];
        int count = 0;
        count += visit(0,rows,0,cols,threshold,visited);
        return count;
    }
    
    public int visit(int i,int rows,int j,int cols,int threshold,boolean[][] visited){
        if(i < 0 || i > rows-1){
            return 0;
        }
        
        if(j < 0 || j > cols-1){
            return 0;
        }
        
        if(visited[i][j] == true){
            return 0;
        }
        
        int count = 0;
        if(canReach(i,j,threshold)){
            visited[i][j] = true;
            count++;
            count += visit(i-1,rows,j,cols,threshold,visited);
            count += visit(i,rows,j-1,cols,threshold,visited);
            count += visit(i+1,rows,j,cols,threshold,visited);
            count += visit(i,rows,j+1,cols,threshold,visited);
        }
        
        return count;
    }
    
    
    public boolean canReach(int i,int j,int threshold){
        
        int total = 0;
        
        do{
            total += i % 10;
            i = i / 10;
        }while(i != 0 && i/10 >= 0);
        
        do{
            total += j % 10;
            j = j / 10;
        }while(j != 0 && j/10 >= 0);
        
        return total <= threshold;
    }
}