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

原题链接：剑指 Offer 13. 机器人的运动范围

 

solution:

        bfs模板题

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只能到达(0,0)
        int ans = 0;    //返回值
        sta = vector<vector<bool>> (m, vector<bool> (n, false));
        queue<PII> que;
        que.push({0,0});    //起点入栈
        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函数计算各位数字之和
    int sum(int x) {
        int ans = 0;
        while(x) {
            ans += x % 10;
            x /= 10;
        }
        return ans;
    }
};