AcWing 24. 24.机器人的运动范围
原题链接
简单
作者:
Wmz1220
,
2023-10-09 11:49:11
,
所有人可见
,
阅读 60
C++ 代码
class Solution {
public:
int get(pair<int,int> a){
int s=0;
while(a.first){
s+=a.first%10;
a.first/=10;
}
while(a.second){
s+=a.second%10;
a.second/=10;
}
return s;
}
int movingCount(int threshold, int rows, int cols)
{
if(!rows||!cols)return 0;
queue<pair<int,int> > q;
vector<vector<bool> > st(rows,vector<bool>(cols,false));
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
int res=0;
q.push({0,0});
while(q.size()){
auto t=q.front();
q.pop();
if(st[t.first][t.second]||get(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;
}
};