面试题13：机器人的运动范围（c++）【剑指offer】

借鉴面试题12.

class Solution {
public:
    int x[4]={0,0,-1,1};
    int y[4]={-1,1,0,0};
    int movingCount(int threshold, int rows, int cols){
        if(threshold<0 || rows<=0 || cols<=0) return 0;
        int num=0;
        vector<vector<bool>> visited(rows,vector<bool>(cols,false));
        dfs(threshold,rows,cols,0,0,num,visited);
        return num;
    }
    int dfs(int threshold,int rows,int cols,int i,int j,int &num,vector<vector<bool>> &visited){
        num++;
        visited[i][j]=true;
        for(int k=0;k<4;k++){
            int d_x=x[k]+i;
            int d_y=y[k]+j;
            int sum=sumP(d_x)+sumP(d_y);
            if(d_x>=0 && d_x<rows && d_y>=0 && d_y<cols){
                if(visited[d_x][d_y]==false && sum<=threshold) dfs(threshold,rows,cols,d_x,d_y,num,visited);
            }
        }
        return 0;
    }
    int sumP(int p){
        int a,sum=0;
        while(p>0){
            sum=sum+p%10;
            p=p/10;
        }
        return sum;
    }
};

改进：

class Solution {
public:
    int movingCount(int threshold, int rows, int cols){
        if(threshold<0 || rows<=0 || cols<=0) return 0;
        vector<vector<bool>> visited(rows,vector<bool>(cols,false));
        return dfs(threshold,rows,cols,0,0,visited);
    }
    int dfs(int threshold,int rows,int cols,int i,int j,vector<vector<bool>> &visited){
        int count=0;
        if(i>=0 && i<rows && j>=0 && j<cols && !visited[i][j]){
            int sum=sumP(i)+sumP(j);
            if(sum<=threshold){
                visited[i][j]=true;
                count=1+dfs(threshold,rows,cols,i,j-1,visited)+dfs(threshold,rows,cols,i,j+1,visited)+
                        dfs(threshold,rows,cols,i-1,j,visited)+dfs(threshold,rows,cols,i+1,j,visited);
            }
        }
        return count;
    }
    int sumP(int p){
        int a,sum=0;
        while(p>0){
            sum=sum+p%10;
            p=p/10;
        }
        return sum;
    }
};