Sword finger offer 13 Range of motion of robot

Original link ： The finger of the sword Offer 13. The range of motion of the robot

 

solution:

        bfs The template questions

class Solution {
public:
    typedef pair<int,int> PII;
    int dx[4] = {-1, 0, 1, 0},dy[4] = {0, -1, 0, 1};
    vector<vector<bool>> sta;
    int movingCount(int m, int n, int k) {
        if(k == 0) return 1;    //k = 0 Only to (0,0)
        int ans = 0;    // Return value 
        sta = vector<vector<bool>> (m, vector<bool> (n, false));
        queue<PII> que;
        que.push({0,0});    // Starting point stack 
        sta[0][0] = true;
        while(!que.empty()) {
            auto t = que.front();
            que.pop();
            ans++;
            for(int i = 0;i < 4;i++) {
                int x = t.first + dx[i];
                int y = t.second + dy[i];
                if(x < 0 || x == m || y < 0 || y == n || sta[x][y] || sum(x) + sum(y) > k) continue;
                sta[x][y] = true;
                que.push({x,y});
            }
        }
        return ans;
    }

    //sum Function to calculate the sum of each digit 
    int sum(int x) {
        int ans = 0;
        while(x) {
            ans += x % 10;
            x /= 10;
        }
        return ans;
    }
};