class Solution {
public:
    int m,n,k;
    int st[50][50] = {0};
    int count = 0;
    int get_sum(int x, int y)
    {
        int sum = 0;
        while(x || y)
        {
            sum += x%10;
            sum += y%10;
            x /= 10;
            y /= 10;
        }

        return sum;
    }
    // 深度优先搜索
    void dfs(int x, int y)
    {
        if(x < 0 || x >= m 
            || y < 0 || y >= n)
        {
            return ;        
        }
        if(st[x][y])
            return;
        if(get_sum(x,y) > k)
            return ;
        count++;
        st[x][y] = 1;
        dfs(x+1, y);
        dfs(x-1, y);
        dfs(x, y+1);
        dfs(x, y-1);
    }
    int movingCount(int threshold, int rows, int cols)
    {

        m = rows;
        n = cols;
        k = threshold;
        dfs(0,0);
        return count;

    }
};