题解 | 机器人的运动范围

#include <vector>
class Solution {
public:

    int getSum(int r, int c){
        int ans = 0;
        while(r){
            ans += r%10;
            r /= 10;
        }
        while(c){
            ans += c%10;
            c /=10;
        }
        return ans;
    }
    void dfs(int threshold, int rows, int cols, int r, int c, vector<vector<bool>>& isD){
        if(r<0||r>=rows||c<0||c>=cols||isD[r][c]||getSum(r, c)>threshold) return;
        isD[r][c] = true;
        int a[] = {1, 0, -1, 0, 0, 1, 0, -1};//一个常见做法来简化搜索方向改变的代码
        for(int i = 0; i < 4; ++i){
            dfs(threshold, rows, cols, r+a[i*2], c+a[i*2+1], isD);
        }
    }
    int movingCount(int threshold, int rows, int cols) {
        //最好不要有全局变量
        if(threshold<0)//不只是字符串需要处理负数和0的情况，但是算法题总是不需要特殊处理就能过
            return -1;
        vector<vector<bool> > isD(rows, vector<bool> (cols, false));
        dfs(threshold, rows, cols, 0, 0, isD);
        int cnt = 0;
		//如果之前有传参让dfs自己加就可以不用遍历了，但是晚上我没有思考这样传会不会在递归的过程中产生问题，有兴趣的读者可以自己想想
        for(int i = 0; i < rows; ++i)
            for(int j = 0; j < cols; ++j)
                if(isD[i][j]) ++cnt;
        return cnt;
        
    }
};

dfs，要注意的点基本上已经标注出来了。时间复杂度是O(m*n*(logm+logn))，空间复杂度是O(m*n)。