CN-12. Robot Path

class Solution {
    public int movingCount(int m, int n, int k) {
        return dp(m, n, k);
    }

    private int dp(int m, int n, int k) {
        boolean[][] dp = new boolean[m][n];

        dp[0][0] = true;
        int sum = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!enterable(i, j, k)) continue;
                if (i - 1 >= 0) dp[i][j] |= dp[i - 1][j];
                if (j - 1 >= 0) dp[i][j] |= dp[i][j - 1];
                if (dp[i][j]) {
                    sum += 1;
                }
            }
        }

        return sum;
    }

    private int dfs(int m, int n, int k) {
        boolean[][] seen = new boolean[m][n];
        return dfsHelper(m, n, 0, 0, k, seen);
    }

    private int dfsHelper(int m, int n, int si, int sj, int k, boolean[][] seen) {
        if (si < 0 || si >= m || sj < 0 || sj >= n || seen[si][sj] || !enterable(si, sj, k)) {
            return 0;
        }
        seen[si][sj] = true;
        return 1 + dfsHelper(m, n, si + 1, sj, k, seen) + dfsHelper(m, n, si, sj + 1, k, seen);
    }

    private int bfs(int m, int n, int k) {
        Queue<int[]> q = new LinkedList<>();
        boolean[][] seen = new boolean[m][n];

        int sum = 0;
        q.add(new int[]{0, 0});
        while (!q.isEmpty()) {
            int[] box = q.remove();
            if (box[0] < 0 || box[0] >= m || box[1] < 0 || box[1] >= n || seen[box[0]][box[1]]) {
                continue;
            }
            seen[box[0]][box[1]] = true;
            if (enterable(box[0], box[1], k)) {
                sum++;
                q.add(new int[]{box[0], box[1] + 1});
                q.add(new int[]{box[0] + 1, box[1]});
            }
        }

        return sum;
    }

    private boolean enterable(int x, int y, int k) {
        int sum = 0;
        while (x != 0) {
            sum += x % 10;
            x /= 10;
        }
        while (y != 0) {
            sum += y % 10;
            y /= 10;
        }
        return sum <= k;
    }
}