LeetCode.剑指offer.013.机器人的运动范围

题目描述

《剑指offer》面试题13. 机器人的运动范围
https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/

地上有一个 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

---

解题过程

一开始没看清题意，以为是每个点的 (x,y) 下标之和不超过 k，提交之后到第20几个测试用例就过不去了。后来看评论才意识到让求的是 数位之和，也就是整数的各位数字之和。
数位之和之所以能够 (x/10 + x%10) + (y/10 + y%10) 这样求，是因为题目规定了 m,n 不超过 100，最多只有3位

很明显是 dfs 或 bfs 来做，一开始我以为 bfs 会更快，都写了一遍发现 dfs 比 bfs 快一个数量级。看来真的不能靠以为。

做完之后才发现，其实并不需要往 下、右下、右 3个方向遍历，只需要往 下、右 两个方向遍历即可。

DFS深度优先搜索

时间复杂度 O(mn)
需要一个 m*n 的数组 visited 来记录是否访问过某结点，避免重复访问死循环，所以空间复杂度 O(mn)

// 深度优先搜索 最快
private static class SolutionV2020_DFS {
    private int count;
    private int rows, columns;
    // 访问过的坐标
    private Set<Pair<Integer, Integer>> visited;

    public int movingCount(int m, int n, int k) {
        count = 0;
        rows = m;
        columns = n;
        visited = new HashSet<>();
        dfs(0, 0, k);
        return count;
    }

    private void dfs(int x, int y, int k) {
        if (x >= rows || y >= columns || (x/10 + x%10) + (y/10 + y%10) > k) {
            return;
        }
        Pair<Integer, Integer> pair = new Pair<>(x, y);
        if (visited.contains(pair)) {
            return;
        }
        count++;
        visited.add(pair);
        // 下
        dfs(x + 1, y, k);
        // 右下
        dfs(x + 1, y + 1, k);
        // 右 ️
        dfs(x, y + 1, k);
    }
}

BFS广度优先搜索-下层结点全部入队

队列实现广度优先搜索，同样需要一个 visited 来标识是否已访问过，因为每次把 下、右下、右 3个方向当做下一层，是会重复的。

时间复杂度 O(mn)，空间复杂度 O(mn)

下面的写法把每个结点的下一层不加判断就放入队列，从队列取出时才判断是否合法。

// BFS，下一层不判断就入队
private static class SolutionV2020_BFS_AllEnQueue {
    public int movingCount(int m, int n, int k) {
        int count = 0;
        Set<Pair<Integer, Integer>> visited = new HashSet<>();
        Queue<Pair<Integer, Integer>> queue = new LinkedList<>();
        queue.offer(new Pair<>(0, 0));
        while (!queue.isEmpty()) {
            Pair<Integer, Integer> pair = queue.poll();
            if (!visited.contains(pair)) {
                visited.add(pair);
                int x = pair.getKey(), y = pair.getValue();
                if (x < m && y < n && (x/10 + x%10 + y/10 + y%10) <= k) {
                    count++;
                    queue.offer(new Pair<>(x+1, y));
                    queue.offer(new Pair<>(x+1, y+1));
                    queue.offer(new Pair<>(x, y+1));
                }
            }
        }
        return count;
    }
}

BFS广度优先搜索-下层的合法结点才入队

时间复杂度 O(mn)，空间复杂度 O(mn)

先对下层结点进行判断，合法的才入队

// BFS，合法的下层结点才入队列
private static class SolutionV2020_BFS_ValidEnQueue {
    public int movingCount(int m, int n, int k) {
        int count = 0;
        Set<Pair<Integer, Integer>> visited = new HashSet<>();
        Queue<Pair<Integer, Integer>> queue = new LinkedList<>();
        queue.offer(new Pair<>(0, 0));
        while (!queue.isEmpty()) {
            Pair<Integer, Integer> pair = queue.poll();
            if (!visited.contains(pair)) {
                visited.add(pair);
                count++;
                int x = pair.getKey(), y = pair.getValue();
                if (valid(x+1, y, m, n, k)) {
                    queue.offer(new Pair<>(x+1, y));
                }
                if (valid(x+1, y+1, m, n, k)) {
                    queue.offer(new Pair<>(x+1, y+1));
                }
                if (valid(x, y+1, m, n, k)) {
                    queue.offer(new Pair<>(x, y+1));
                }
            }
        }
        return count;
    }

    // 判断(x,y)是否合法
    private boolean valid(int x, int y, int m, int n, int k) {
        if (x < m && y < n && (x / 10 + x % 10 + y / 10 + y % 10) <= k) {
            return true;
        }
        return false;
    }
}

---

GitHub代码

algorithms/leetcode/offer/_013_RobotMovingCount.java
https://github.com/masikkk/algorithms/blob/master/leetcode/offer/_013_RobotMovingCount.java

---