题解 | #机器人的运动范围#

基本思路：要到达一个点首先需要它四周有点可到达，然后才是它自己满足条件，可以想到基本框架用BFS搜索。然后，这个点自己需要满足的条件如下：

• 它在规定的行坐标和列坐标范围内：在队列添加下一个点时简单判断即可
• 它的行列各位数之和小于等于threshold：在队列添加下一个点时加和判断即可
• 它不能被重复计数：用哈希表存储已统计过的点，因为哈希表没有内置的对pair的哈希算法，所以需要自己实现（当然用vector自己实现也可以）

class Solution {
public:
    struct pair_hash {
        inline size_t operator()(const pair<int,int> & p) const {
            return p.first * 101 + p.second;
        }
    };

    unordered_set<pair<int, int>, pair_hash> hash;
    vector<vector<int>> neigh = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    bool judge(int x, int y, int rows, int cols, int threshold) {
        if (!(x >= 0 && x < rows && y >= 0 && y < cols)) return false;
        int res = 0;
        while (x) {
            res += x % 10;
            x /= 10;
        }
        while (y) {
            res += y % 10;
            y /= 10;
        }
        return res <= threshold;
    }

    int movingCount(int threshold, int rows, int cols) {
        int res = 0;
        queue<pair<int, int>> q;
        q.emplace(0, 0);
        hash.insert(make_pair(0, 0));
        while (!q.empty()) {
            auto now = q.front();
            res++;
            q.pop();
            for (auto &i: neigh) {
                int x = now.first + i[0], y = now.second + i[1];
                if (judge(x, y, rows, cols, threshold) && !hash.count(make_pair(x, y))) {
                    q.emplace(x, y);
                    hash.insert(make_pair(x, y));
                }
            }
        }
        return res;
    }
};