这个题,我在check函数中掉了一下坑,开始没抽离check函数,忘了改变i,j的值,会导致后面的dfs出错。
总体不难,就是一个dfs跟一个check函数的就搞定了。没有复杂操作,大部分人注意下check的细节就没有问题了。
class Solution {
public:
int movingCount(int threshold, int rows, int cols) {
int res = 0;
vector <vector<int>> record(rows,vector<int>(cols,0));
dfs(record, 0, 0, res,threshold);
return res;
}
bool check(int i,int j,int threshold){
int num = 0;
while(i>=10){
num += (i % 10);
i = i/10;
};
while(j>=10){
num += (j % 10);
j = j/10;
};
num += (i % 10);
num += (j % 10);
return num <= threshold;
}
void dfs(vector <vector<int>> &record,int i,int j,int &res,int threshold){
if(i < 0 || i >= record.size() || j < 0 || j >= record[i].size() || record[i][j] == 1){
return;
}
record[i][j] = 1;
if(!check(i,j,threshold)){
return;
}
res += 1;
dfs(record, i-1, j, res, threshold);
dfs(record, i+1, j, res, threshold);
dfs(record, i, j-1, res, threshold);
dfs(record, i, j+1, res, threshold);
}
};



京公网安备 11010502036488号