AcWing 24. 机器人的运动范围
原题链接
简单
作者:
跟着灿哥学切菜
,
2021-02-01 10:55:27
,
所有人可见
,
阅读 306
class Solution {
public:
int get_sum(pair<int, int> p) {
int s = 0;
while (p.first) {
s += p.first % 10;
p.first /= 10;
}
while (p.second) {
s += p.second % 10;
p.second /= 10;
}
return s;
}
int movingCount(int threshold, int rows, int cols) {
//如果此时行为0或者列为0, 此时直接返回的是0个格子
if (!rows || !cols) return 0;
//使用队列来记录每一个位置上的坐标, 因为每一个位置上的坐标都是由两个数值控制, 所以此时使用pair来完成
queue<pair<int, int>> q;
//定义一个二维的矩阵来记录其中的格子是否已经遍历过
vector<vector<bool>> st(rows, vector<bool>(cols, false));
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
int res = 0;
q.push({0, 0});
while (q.size()) {
//首先将队列的队头元素取出来
auto t = q.front();
q.pop();
//如果当前的这个位置已经遍历过, 或者此位置上的坐标和已经大于threshold, 此时过滤掉
if(st[t.first][t.second] || get_sum(t) > threshold) continue;
res ++;
st[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;
}
};