leetcode面试题13. 机器人的运动范围

leetcode面试题13. 机器人的运动范围

四月 11, 2020

leetcode面试题13. 机器人的运动范围

地上有一个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：
输入：m = 2, n = 3, k = 1
输出：3

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

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

经典的dfs和bfs搜索。
bfs版好理解，线上bfs版、

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
class Solution {
    public int movingCount(int m, int n, int k) {
        int count = 0;
        int[][] direction = {{0,1},{1,0}};
        int[][] visited = new int[m][n];
        visited[0][0] = 1;
        count = 1;
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0,0});
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int x = cur[0];
            int y = cur[1];
            for (int i = 0; i < 2; i++) {//四个方向，仔细想其实两个方向右和下就够了，
            //只有两个方向就可以到达全部的点
                int nextx = x + direction[i][0];
                int nexty = y + direction[i][1];
                //三种情况，越界，访问过，不满足题意
                if (nextx < 0 || nexty < 0 || nextx > m - 1 || nexty > n - 1) continue;
                if (visited[nextx][nexty] == 1) continue;
                boolean flag = judge(nextx,nexty,k);
                if (!flag) continue;
                visited[nextx][nexty] = 1;
                queue.offer(new int[]{nextx,nexty});
                count++;
            }
        }
        return count;
    }
    public boolean judge(int nextx, int nexty, int k) {
        return (getSum(nextx) + getSum(nexty)) <= k;
    }
    public int getSum(int a) {//求位数和
        if (a == 0) return 0;
        return a % 10 + getSum(a / 10);
    }
}

dfs

dfs和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
class Solution {
    public int movingCount(int m, int n, int k) {
        visited = new int[m][n];
        return dfs(0,0,k);
    }
    private int[][] visited;
    public int dfs(int x, int y, int k) {
        if (x < 0 || y < 0 || x > visited.length - 1 || y > visited[0].length - 1) return 0;
        if (visited[x][y] == 1) return 0;
        if (!judge(x, y, k)) return 0;
        visited[x][y] = 1;
        int ans = 1;//自己1个节点
        int[][] direction = {{0,1},{1,0},{0,-1},{-1,0}};
        for (int i = 0; i < 4; i++) {
            int nextx = x + direction[i][0];
            int nexty = y + direction[i][1];
            ans += dfs(nextx, nexty,k);
        }
        return ans;
    }
    public boolean judge(int nextx, int nexty, int k) {
        return (getSum(nextx) + getSum(nexty)) <= k;
    }
    public int getSum(int a) {//求位数和
        if (a == 0) return 0;
        return a % 10 + getSum(a / 10);
    }
}

leetcode 73/100