机器人大冒险（能否到达终点）

一、题目

题目来源 LeetCode link

​ 力扣团队买了一个可编程机器人，机器人初始位置在原点(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]不为原点或者终点

二、解题思路

思路一

暴力解法。（超出内存限制）

创建一个二维矩阵，在遍历obstacles，在每个障碍处做标记，然后循环command，遇到障碍，则返回false，最后到达终点则返回true。

思路二

空间复杂度O(1)，时间复杂度O(m*n) m为command的长度，n为obstacles的长度

​ 题目要求command是循环走的，则每走一遍的x增加值、y增加值都是相同的。如“RUU"，(R向右走，x+1;U向上走，y+1)每走一遍，则x+1，y+2。对于目的地x，y，让机器人先走k轮命令，( k=MIN{x / x_1, y / y_1} )，再走下一轮就到达或者超过目标点了，即走k轮后到达离终点距离只有一轮命令的位置。然后走一轮命令来判断是到达目的点还是超过目的点。

例如：指令 “URR” 执行完毕停留在（2,1）这个点，假若终点是（10000,5001），那么机器人执行 5000 次指令到达终点附近的点（10000，5000），在走下一轮时，就会到达终点。

方法boolean isArrive(String command, int x_0, int y_0, int x_tar, int y_tar)用来判断从点x_0,y_0走一轮command是否到达x_tar,y_tar。

第一步

​ 首先判断是否能到达终点，如果终点都到不了，就不用考虑障碍物了，直接return false。

第二步

​ 遍历obstacles[][] 数组中的每一个障碍物，如果机器人能到达障碍物，则return false。

三、代码

java

public class Rebot {
    public static boolean robot(String command, int[][] obstacles, int x, int y) {
        //x_1,y_1为走过一遍指令后的变化值
        int x_1 = 0, y_1 = 0;
        int k;
        for (int i = 0; i < command.length(); i++) {
            if (command.charAt(i) == 'U') {
                y_1++;
            } else {
                x_1++;
            }
        }
        //k表示走k遍指令
        k = Math.min(x / x_1, y / y_1);
        //x_tar,y_tar代表走过k轮后，剩下的距离
        int x_tar = x - k * x_1;
        int y_tar = y - k * y_1;
        //判断是否能到达终点
        if (!isArrive(command, 0, 0, x_tar, y_tar)) {
            return false;
        }
        //判断障碍物是否在行走路线上
        for (int i = 0; i < obstacles.length; i++) {
            k = Math.min(obstacles[i][0] / x_1, obstacles[i][1] / y_1);
            x_tar = obstacles[i][0] - k * x_1;
            y_tar = obstacles[i][1] - k * y_1;
            //只判断在目标点范围内的障碍物
            if (obstacles[i][0] <= x && obstacles[i][1] <= y && isArrive(command, 0, 0, x_tar, y_tar)) {
                return false;
            }
        }
        return true;
    }

    //判断机器人能否从起始点x_0,y_0到达一个目标点x_tar,y_tar
    //x_1,y_1为当前位置,x,y为目标位置
    public static boolean isArrive(String command, int x_0, int y_0, int x_tar, int y_tar) {
        for (int i = 0; i < command.length(); i++) {
            //判断目标点和起始点是否重合
            if (x_0 == x_tar && y_0 == y_tar) {
                return true;
            }
            //执行一轮命令
            if (command.charAt(i) == 'U') {
                y_0++;
            } else {
                x_0++;
            }
        }
        return false;
    }
}