class Solution {
public:
    int cal(int x,int y)
    {
        int res=0;
        while(x)
        {
            res+=x%10;
            x/=10;
        }
        while(y)
        {
            res+=y%10;
            y/=10;
        }
        return res;
    }
    int movingCount(int k, int m, int n)
    {
        if(m==0||n==0)return 0;
        int dx[4]={1,-1,0,0};
        int dy[4]={0,0,1,-1};
        int cnt=0;
        int st[51][51];
        memset(st, 0, sizeof st);
        pair<int,int> start={0,0};
        st[start.first][start.second]=1;
        cnt++;
        queue<pair<int,int>> q;
        q.push(start);
        while(!q.empty())
        {
            pair<int,int> u=q.front();
            q.pop();
            for(int i=0;i<4;i++)
            {
                int x=u.first+dx[i];
                int y=u.second+dy[i];
                if(x>=0&&x<m&&y>=0&&y<n&&cal(x,y)<=k&&st[x][y]==0)
                {
                    st[x][y]=1;
                    cnt++;
                    q.push({x,y});
                }
            }
        }
        return cnt;
    }
}