24. 机器人的运动范围
作者:
catlle
,
2022-10-31 17:45:17
,
所有人可见
,
阅读 195
class Solution {
public:
const int N = 100;
//计算每个方格的和
int judge(int n, int m){
int sum = 0;
while(n){
sum += n % 10;
n /= 10;
}
while(m){
sum += m % 10;
m /= 10;
}
return sum;
}
int movingCount(int threshold, int rows, int cols)
{
int res = 0;
if(!rows || !cols)
return 0;
queue<pair<int, int>> q;
vector<vector<bool>> map(rows, vector<bool>(cols, false));
q.push({0,0});
//上右下左
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
while(q.size()){
//将队列里的元素拿出来
auto t = q.front();
q.pop();
//判断该元素是否合理
if(judge(t.first, t.second) > threshold || map[t.first][t.second])
continue;
res++;
//标记已去过的方格
map[t.first][t.second] = true;
//上右下左进行操作
for(int i = 0; i < 4; i++){
int x = t.first + dx[i], y = t.second + dy[i];
if(x >= 0 && x < rows && y >= 0 && y < cols){
q.push({x, y});
}
}
}
return res;
}
};