这个题,我在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); } };