code4offer-13 机器人的运动范围

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

Description

地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？

示例 1：

1
2
输入：m = 2, n = 3, k = 1
输出：3

示例 2：

1
2
输入：m = 3, n = 1, k = 0
输出：1

提示：

1
2
- 1 <= n,m <= 100
- 0 <= k <= 20

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

Analyse

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
class Solution {
    private int[] rowDirection = {0, 0, -1, 1};
    private int[] colDirection = {-1, 1, 0, 0};
 
    // 0 未走
    // -1 不能走
    // 1 已走
    private int[][] grid;

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

        // 先mark所有非法的坐标
        for (int i = 0;i < m; i++) {
            for (int j = 0; j < n; j++) {
                grid[i][j] = isLargeThanK(i, j, k) ? -1 : 0;
            }
        }
        return helper(0, 0, k, m, n);
    }

    private int helper(int startX, int startY, int k, int m, int n) {
        // base case
        if (!isValid(startX, startY, m, n) || grid[startX][startY] != 0) {
            return 0;
        }

        grid[startX][startY] = 1;

        int count = 0;

        // recursive case
        for (int i = 0; i < 4; i++) {
            int x = startX + rowDirection[i];
            int y = startY + colDirection[i];

            if (!isValid(x, y, m, n) || grid[x][y] != 0) continue;

            // choose it
            count += helper(x, y, k, m, n);
        }

        return count + 1;
    }

    private boolean isValid(int x, int y, int m, int n) {
        if (x < 0 || x >= m) return false;
        if (y < 0 || y >= n) return false;

        return true;
    }

    // x y的数位之和不能大于k
    private boolean isLargeThanK(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;
        }

        if (sum > k) {
            return true;
        }

        return false;
    }
}

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
44
class Solution {
    private int[] rowDirection = {0, 1};
    private int[] colDirection = {1, 0};
 
    // 0 未走
    // -1 不能走
    // 1 已走
    private int[][] grid;

    private int getSum(int x, int s_x) {
        return (x+1) % 10 != 0 ? s_x + 1 : s_x - 8;
    }

    public int movingCount(int m, int n, int k) {
        grid = new int[m][n];
    
        int count = 0;

        Deque<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[]{0,0,0,0});

        while (!queue.isEmpty()) {
            int[] point = queue.poll();
            int x = point[0], y = point[1], s_x = point[2], s_y = point[3];

            if (!isValid(x, y, m, n) || s_x + s_y > k || grid[x][y] != 0) continue;

            grid[x][y] = 1;
            count++;

            queue.offer(new int[]{x+1, y, getSum(x, s_x), s_y});
            queue.offer(new int[]{x, y+1, s_x, getSum(y, s_y)});
        }

        return count;
    }

    private boolean isValid(int x, int y, int m, int n) {
        if (x < 0 || x >= m) return false;
        if (y < 0 || y >= n) return false;

        return true;
    }  
}