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

class Solution {
public:
    //记录四个方向
    int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
    //记录答案
    int res=0;
    //标记访问格子
    int flag[101][101];
    //计算一个数字的每个数之和
    int cal(int n) {
        int sum=0;
        while(n) {
            sum+=(n%10);
            n/=10;
        }
        return sum;
    }
    void dfs(int i,int j,int threshold,int rows,int cols) {
        //如果行列和数字相加大于threshold
        if(cal(i)+cal(j)>threshold) return;
        //如果越界或者已经访问过
        if(i<0||i>=rows||j<0||j>=cols||flag[i][j]) return;
        res+=1;
        flag[i][j]=1;
        //遍历所有方向
        for(int k=0;k<=3;k++) {
            dfs(i+dir[k][0],j+dir[k][1],threshold,rows,cols);
        }
    }
    int movingCount(int threshold, int rows, int cols) {
        dfs(0,0,threshold,rows,cols);
        return res;
    }
};