class Solution {
public:

    int get_sum(int fir, int sec)
    {
        int ans = 0;
        string its = to_string(fir) + to_string(sec);
        for (int i = 0; i < its.length(); ++i) ans += its[i] - '0';
        return ans;
    }

    int movingCount(int threshold, int rows, int cols)
    {
        //经典的宽度优先搜索问题
        queue<pair<int, int>>buff;
        vector<vector<bool>>flag(rows, vector<bool>(cols, false));
        int ans = 0;
        if (!cols || !rows) return ans;
        //方向向量
        int dx[4] = {-1, 1, 0 , 0}; int dy[4] = {0, 0, -1, 1};
        //初始化队列
        buff.push({0, 0});
        while(buff.size()) {
            auto t = buff.front();
            buff.pop();

            int x = t.first, y = t.second;
            //如果当前的点已经被访问过，或者当前的点不能被到达，直接返回
            if (flag[x][y] || get_sum(x, y) > threshold) continue;
            //符合规则;标记访问过
            ans++; flag[x][y] = true;
            //模板：BFS的四个方向
            for (int i = 0; i < 4; ++i) {
                if (x + dx[i] < rows && x + dx[i] >= 0 && y + dy[i] < cols && y + dy[i] >= 0)
                    buff.push({x + dx[i], y + dy[i]});
            }
        }
        return ans;
    }
};