class Solution {
    int n;
    int m;
    int k;
    int[] dx = {-1, 0, 1, 0};
    int[] dy = {0, 1, 0, -1};
    boolean[][] vis;
    public int movingCount(int k, int n, int m) { // 为了方便起见改成k，n，m。我习惯用n代表行，m代表列😂
        if (n == 0 || m == 0) return 0;
        this.n = n;
        this.m = m;
        this.k = k;
        vis = new boolean[n][m];
        return dfs(0, 0);
    }
    public int dfs(int x, int y) {
        int ans = 0;
        if (!check(x, y)) return ans;
        else {
            ans++;
            vis[x][y] = true;
        }
        for (int i = 0; i < 4; i++) {
            int a = x + dx[i], b = y + dy[i];
            if (a < 0 || a >= n || b < 0 || b >= m || vis[a][b]) continue;
            ans += dfs(a, b);
        }
        return ans;
    }
    public boolean check(int a, int b) {
        int ans = 0;
        while (a > 0) {
            ans += a % 10;
            a /= 10;
        } 
        while (b > 0) {
            ans += b % 10;
            b /= 10;
        }
        return ans <= k;
    }
}