剑指 Offer 13. 机器人的运动范围

剑指 Offer 13. 机器人的运动范围

思路：

搜索的方式是上下左右，如果在范围之内且和满足条件才去搜索，每次搜索答案 + 1。

代码：

class Solution {
public:
    int getsum(int x){
        if(!x) return 0;
        return getsum(x / 10) + x % 10;
    }

    int res = 0;
    int k;
    int n,m;
    vector<vector<bool>> st;
    int dx[4] = {0 , 1, 0, -1},dy[4] = {1 ,0 ,-1, 0};

    int movingCount(int _m, int _n, int _k) {
        st = vector<vector<bool>> (_m + 1,vector<bool> (_n + 1,false));

        k = _k;
        n = _m;
        m = _n;

        dfs(0,0);
        return res;
    }

    void dfs(int x,int y){
        res++;
        st[x][y] = true;
        for(int i = 0; i < 4; i++){
            int a = x + dx[i],b = y + dy[i];
            int sum = getsum(a) + getsum(b);
            if(a >= 0 && a < n && b >= 0 && b < m && !st[a][b] && sum <= k){
                dfs(a,b);
            }
        }
    }
};