AcWing 24. 机器人的运动范围(DFS+BFS)
1.DFS
从起点位置开始深入,遇到合法位置则计数器自增,否则返回。由于题目不需要回溯,因此访问数组不必还原。
具体代码如下:
class Solution {
public:
int dx[2] = {0, 1}; //根据题意可以发现只需要有两个方向即可
int dy[2] = {1, 0};
//计算数位和
int getSum(int x, int y){
int t = 0;
while(x){
t += x % 10;
x /= 10;
}
while(y){
t += y % 10;
y /= 10;
}
return t;
}
void dfs(vector<vector<int>> &visit, int x, int y, int &sum, int &th)
{
if(getSum(x, y) > th) return; //当前位置的坐标数位和大于阈值,故返回
visit[x][y] = 1;
sum++;
for(int i = 0; i < 2; i++){
int newx = x + dx[i], newy = y + dy[i];
if(newx < visit.size() && newy < visit[0].size() && visit[newx][newy] == 0){
dfs(visit, newx, newy, sum, th);
}
}
}
int movingCount(int threshold, int rows, int cols)
{
if(rows == 0) return 0;
vector<vector<int>> visit(rows, vector<int> (cols, 0));
int sum = 0;
dfs(visit, 0, 0, sum, threshold);
return sum;
}
};
2.BFS
相比于AcWing 23. 矩阵中的路径(DFS),这道题就可以使用BFS求解。因为这道题不是对指定次序的序列进行查找判断,而是对单点进行查找判断。
具体代码如下:
class Solution {
public:
int dx[2] = {0, 1}; //根据题意可以发现只需要有两个方向即可
int dy[2] = {1, 0};
//计算数位和
int getSum(int x, int y){
int t = 0;
while(x){
t += x % 10;
x /= 10;
}
while(y){
t += y % 10;
y /= 10;
}
return t;
}
int movingCount(int threshold, int rows, int cols)
{
if(rows == 0) return 0;
vector<vector<int>> visit(rows, vector<int> (cols, 0));
queue<pair<int, int>> q;
int sum = 0;
q.push({0, 0}); //根据题意,起点一定满足条件,所以这里直接压入队列没做判断
visit[0][0] = 1;
while(!q.empty()){
int x = q.front().first, y = q.front().second;
q.pop();
sum++;
for(int i = 0; i < 2; i++){
int newx = x + dx[i], newy = y + dy[i];
if(newx >= rows || newy >= cols || getSum(newx, newy) > threshold || visit[newx][newy])
continue;
q.push({newx, newy});
visit[newx][newy] = 1;
}
}
return sum;
}
};