class Solution {
public:
    int get_sum(int x)
    {
        int sum=0;
        int tmp=x;
        while(tmp!=0)
        {
            sum+=tmp%10;
            tmp/=10;
        }
        return sum;
    }
    int movingCount(int threshold, int rows, int cols)
    {
        int res=0;
        #define x first
        #define y second
        #define inf 0x3f3f3f3f
        const int N=110;
        typedef pair<int,int> PII;
        int dist[N][N];
        int k=threshold,m=rows,n=cols;
        if(n==0||m==0) return 0;
        memset(dist,false,sizeof dist);
        queue<PII> Q;
        int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
        dist[0][0]=true;
        Q.push({0,0});
        while(!Q.empty())
        {
            PII t=Q.front();Q.pop();
            res++;
            for(int i=1;i<=4;i++)
            {
                int a=t.x+dx[i],b=t.y+dy[i];
                if(a>=0&&a<n&&b>=0&&b<m&&get_sum(a)+get_sum(b)<=k&&dist[a][b]==false) 
                {
                    dist[a][b]=true;
                    Q.push({a,b});
                }
            }
        }
        return res;
    }
};