剑指 Offer 13. 机器人的运动范围

,

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    private static class CountHolder {
        private int count;
    }

    public int movingCount(int m, int n, int k) {
        boolean[][] used = new boolean[m][n];
        CountHolder countHolder = new CountHolder();
        dfs(used, 0, 0, countHolder, m, n, k);
        return countHolder.count;
    }

    private void dfs(boolean[][] used, int i, int j, CountHolder countHolder, int m, int n, int k) {
        if (i >= m || j >= n || used[i][j]) {
            return;
        }

        if (sumOfDigits(i) + sumOfDigits(j) <= k) {
            countHolder.count++;
            used[i][j] = true;
            dfs(used, i + 1, j, countHolder, m, n, k);
            dfs(used, i, j + 1, countHolder, m, n, k);
        }
    }

    private int sumOfDigits(int num) {
        int sum = 0;
        while (num > 0) {
            sum += num % 10;
            num /= 10;
        }
        return sum;
    }
}

BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
    private static class Point {
        private int i;
        private int j;

        public Point(int i, int j) {
            this.i = i;
            this.j = j;
        }
    }

    public int movingCount(int m, int n, int k) {
        boolean[][] used = new boolean[m][n];

        Queue<Point> queue = new LinkedList<>();
        queue.offer(new Point(0, 0));

        int count = 0;

        while (!queue.isEmpty()) {
            Point point = queue.poll();
            int i = point.i, j = point.j;
            if (i < m && j < n && !used[i][j] && sumOfDigits(i) + sumOfDigits(j) <= k) {
                used[i][j] = true;
                count++;

                queue.offer(new Point(i + 1, j));
                queue.offer(new Point(i, j + 1));
            }
        }

        return count;
    }

    private int sumOfDigits(int num) {
        int sum = 0;
        while (num > 0) {
            sum += num % 10;
            num /= 10;
        }
        return sum;
    }
}

References

剑指 Offer 13. 机器人的运动范围