搜索与回溯

class Solution {
public:
    int get_single_sum(int x){
        int s = 0;
        while(x){
            s += x % 10;
            x /= 10;
        }
        return s;
    }
    int get_sum(pair<int, int> p){
        return get_single_sum(p.first) + get_single_sum(p.second);
    }

    int movingCount(int m, int n, int k) {  
        int res = 0;
        if(!n || !m) return 0; //判断边界

        vector<vector<bool>> st(m, vector<bool>(n));
        queue<pair<int, int>> q;

        q.push({0, 0});

        int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
        while(q.size()){
            auto t = q.front();
            q.pop();
            if(get_sum(t) > k || st[t.first][t.second]) continue;
            res++;
            st[t.first][t.second] = true;
            for(int i = 0; i < 4; i++){
                int x = t.first + dx[i], y = t.second + dy[i];
                if(x >= 0 && x < m && y >= 0 && y < n){
                    q.push({x, y});
                }
            }
        }
        return res;
    }
};