🌕🌕 LCP 03. 机器人大冒险

难度: 🌕🌕

问题描述

---

解法

class Solution {
    int diffx;
    int diffy;
    HashSet<String> set = new HashSet<>(); // 记录初始周期能到达的所有位置
    public boolean robot(String command, int[][] obstacles, int x, int y) {
        // 思路：
        // 当 x & y 过大时，无法通过模拟，超出时间范围
        // 每周期运行后，diffx & diffy 是确定的，因此可以得出 
        // x & y 在无障碍物的情况下，对应初始周期的哪个位置，判断初始周期中这个下标能否达到即可
        // 而对于障碍物，需要保证在达到终点之前，无法达到才能保证无法遇到
        int len = command.length();
        // 计算每个周期的 x & y 变化量
        diffx = 0;
        diffy = 0;
        set.add("0#0");
        for(int i = 0; i < len; i ++) {
            char c = command.charAt(i);
            if(c == 'U') {
                diffy ++;
            } else {
                diffx ++;
            }
            StringBuilder sb = new StringBuilder();
            sb.append(diffx).append('#').append(diffy);
            set.add(sb.toString());
        }
        // 判断无障碍物的情况下能否到达 (x, y)
        if(!isValid(command, x, y)) {
            return false;
        }
        // 遍历障碍物，保证在到达 (x, y) 之前没有遇到障碍物
        for(int[] cur: obstacles) {
            if(cur[0] >= x && cur[1] >= y) {
                continue;
            }
            if(isValid(command, cur[0], cur[1])) {
                return false;
            }
        }
        return true;
    }

    private boolean isValid(String command, int x, int y) {
        int count = Math.min(x / diffx, y / diffy);
        int a = x - diffx * count;
        int b = y - diffy * count; // 对应初始周期的下标值
        // 判断能否到达 (a, b)
        int len = command.length();
        String str = "" + a + "#" + b;
        return set.contains(str);
    }
}

---

输出