LeetCode brush diary: LCP 03. Machine's adventure

力扣团队买了一个可编程机器人,机器人初始位置在原点(0, 0).小伙伴事先给机器人输入一串指令command,机器人就会无限循环这条指令的步骤进行移动.指令有两种：

U: 向y轴正方向移动一格
R: 向x轴正方向移动一格.
不幸的是,在 xy 平面上还有一些障碍物,他们的坐标用obstacles表示.机器人一旦碰到障碍物就会被损毁.

给定终点坐标(x, y),返回机器人能否完好地到达终点.如果能,返回true;否则返回false.
示例 1：

输入：command = "URR", obstacles = [], x = 3, y = 2
输出：true
解释：U(0, 1) -> R(1, 1) -> R(2, 1) -> U(2, 2) -> R(3, 2).

示例 2：

输入：command = "URR", obstacles = [[2, 2]], x = 3, y = 2
输出：false
解释：机器人在到达终点前会碰到(2, 2)的障碍物.

示例 3：

输入：command = "URR", obstacles = [[4, 2]], x = 3, y = 2
输出：true
解释：到达终点后,再碰到障碍物也不影响返回结果.

限制：

2 <= command的长度 <= 1000
command由U,R构成,且至少有一个U,至少有一个R
0 <= x <= 1e9, 0 <= y <= 1e9
0 <= obstacles的长度 <= 1000
obstacles[i]不为原点或者终点

思路：模拟（超时）

class Solution {
    
    public boolean robot(String command, int[][] obstacles, int x, int y) {
    
        int len = command.length();
        int a = 0, b = 0;
        int index = 0;
        while (len != 0){
    
            if(index == len){
    
                index = 0;
            }
            char str = command.charAt(index++);
            if(str == 'U'){
    
                b ++;
            }else if(str == 'R'){
    
                a ++;
            }
            if(a == x && b == y){
    
                return true;
            }else if(a > x || b > y){
    
                return false;
            }
            for (int i = 0; i < obstacles.length; i++) {
    
                if(obstacles[i][0] == a && obstacles[i][1] == b){
    
                    return false;
                }
            }
        }
        return false;
    }
}

优化

class Solution {
    
    public boolean robot(String command, int[][] obstacles, int x, int y) {
    
        int len = command.length();
        int a = 0, b = 0;
        // First judge whether you can finish one round first.
        for (int i = 0; i < len; i++) {
    
            char str = command.charAt(i);
            if(str == 'U'){
    
                b ++;
            }else{
    
                a ++;
            }
        }
        boolean res = reach(command, x, y, a, b);

        if (!res){
    
            return false;
        }
        for (int[] val: obstacles) {
    
            if(val[0] > x || val[1] > y){
    
                continue;
            }
            if(reach(command, val[0], val[1], a, b)){
    
                return false;
            }
        }
        return true;
    }
    public boolean reach(String command,int tx, int ty, int x, int y){
    
        // See how many more passes it will take to get to the end.
        int min = Math.min(tx/x, ty/y);
        int nx = x*min, ny = y*min;
        if(nx == tx && ny == ty){
    
            return true;
        }
        for (int i = 0; i < command.length(); i++) {
    
            char str = command.charAt(i);
            if(str == 'U'){
    
                ny ++;
            }else{
    
                nx ++;
            }
            if (nx > tx || ny > ty) return false;
            if (nx == tx && ny == ty) return true;
        }
        return true;
    }
}