2021.11.02
本题是一道非常基础的01-BFS
只需要记录能够到达多少个位置作为答案
这类问题无需优先队列找最短路（用于有权边的题目中）
只需要queue即可，每个点入队后扩展4个点，并且记录是否来过
理论上每个点只会被入队一次,时间复杂度为O(nm)

小技巧：

• n * m 小于 int范围可以用一个int来同时存储x，y坐标，不用pair

• 取一个mod > m，xy = x * mod + y,因为y <= m < mod，所以y的取值不会影响x

• 去除pair后可以用一个dxy来代替dx和dy 具体实现为 dxy[4] = {1,-1,mod,-mod};

const int N = 55, sk = 100;
class Solution {
public:
    int step, n, m, dxy[4] = {-1,1,100,-100};
    bool st[N][N];

    //bfs常用value函数简化代码
    //这里的value不仅要看x，y是否在范围内，还有x，y是否满足位数和小于threshold
    bool value(int x, int y){
        if(x < 0 || x >= n || y < 0 || y >= m) return 0;
        int tmp = 0;
        for(int i = x; i; i /= 10) tmp += i % 10;
        for(int i = y; i; i /= 10) tmp += i % 10;
        return tmp <= step;//是否满足条件
    }

    int movingCount(int threshold, int rows, int cols)
    {
        if(rows == 0 || cols == 0) return 0;//特例特判
        int ans = 1;//(0,0)算一个位置
        queue<int> q; q.push(0);//将(0,0)入队
        st[0][0] = 1, n = rows, m = cols, step = threshold;//定义为全局变量

        while(q.size()){
            int a = q.front(); //当前坐标
            q.pop();//出队

            for(int i = 0; i < 4; i++){
                int na = a + dxy[i];//下一个坐标
                int nx = na / sk, ny = na % sk;//得到下一个坐标的x，y值
                if(value(nx, ny) && st[nx][ny] == 0)//如果满足条件且没被遍历过
                {
                    q.push(na);//下一个坐标入队
                    st[nx][ny] = 1;//标记入队过
                    ans ++;//答案加一
                }
            }
        }

        return ans;//返回答案
    }
};