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

class Solution {
public:
    int movingCount(int threshold, int rows, int cols) {
        if(rows == 0 && cols == 0) return 0;  //特殊情况判断
        int rec[rows][cols],use[rows][cols];  //rec用于记录当前格子是否符合要求，use用于记录当前格子是否已经考虑过
        int res = 0;  //返回的结果数
        for(int i = 0; i < rows; i ++) {   //这一层循环用于对rec初始化，符号进入条件填0，否则填1
            for(int j = 0;j < cols; j ++) {
                int sum = 0,a = i,b = j;   //sum用于记录横纵坐标各位之和
                while(a != 0){
                    sum += a % 10;
                    a = a / 10;
                }
                while(b != 0){
                    sum += b % 10;
                    b = b / 10;
                }
                if(sum > threshold) rec[i][j] = 1;
                else rec[i][j] = 0;
            }
        }
        for(int i = 0; i < rows; i ++) {   //初始化use，0代表当前格子没有被计算过
            for(int j = 0;j < cols; j ++) use[i][j] = 0;
        }
        queue<pair<int,int>> que;  //定义队列模拟广度优先BFS
        que.push({0,0});  //插入0，0
        use[0][0] = 1;  //更改use0，0
        while(que.size() != 0){  //队不空，就一直访问，直到队空，每次寻找下边的和右边的格子
            if(que.front().first + 1 < rows && rec[que.front().first + 1][que.front().second] == 0 && use[que.front().first + 1][que.front().second] == 0){
                que.push({que.front().first + 1,que.front().second});
                use[que.front().first + 1][que.front().second] = 1;
            } //如果下边格子满足条件，坐标入队，更改use标记
            if(que.front().second + 1 < cols && rec[que.front().first][que.front().second + 1] == 0 && use[que.front().first][que.front().second + 1] == 0){
                que.push({que.front().first,que.front().second + 1});
                use[que.front().first][que.front().second + 1] = 1;
            } //如果右边格子满足条件，坐标入队，更改use标记
            que.pop();  //队头出队，队列中都是满足条件的格子，res++
            res++;
        }
        return res;
    }
};