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

首先我们构建第一个功能,无限循环编程指令,以及加载起点

func robot(command string, obstacles [][]int, x int, y int) bool {
    rx,ry:=0,0
    
    for i:=0;i<len(command);i++{
        switch command[i]{
            case 'R':rx++;break;
            case 'U':ry++;break;
        }
        //Some Code
        if i==len(command)-1{
            i=-1
        }
    }
}

到达终点的条件为rx,ry为函数传入函数的x,y

func robot(command string, obstacles [][]int, x int, y int) bool {
    rx,ry:=0,0
    
    for i:=0;i<len(command);i++{
        switch command[i]{
            case 'R':rx++;break;
            case 'U':ry++;break;
        }
        if rx==x&&ry==y{
            return true
        }
        //Some Code
        if i==len(command)-1{
            i=-1
        }
    }
}

接下来添加对障碍物的判断

func robot(command string, obstacles [][]int, x int, y int) bool {
    rx,ry:=0,0
    
    for i:=0;i<len(command);i++{
        switch command[i]{
            case 'R':rx++;break;
            case 'U':ry++;break;
        }
        for i:=range obstacles{
            if rx==obstacles[i][0]&&ry==obstacles[i][1]{
                return false    //即撞毁
            }
        }


        if rx==x&&ry==y{
            return true
        }
        if i==len(command)-1{
            i=-1
        }
    }
}

其实此题的精髓并不是以上程序的构建,而是对障碍物剔除的逻辑 举个例子,对于终点以外的障碍物我们可以置之不理

if obstacles[i][0]>x||obstacles[i][1]>y{
    obstacles=append(obstacles[i-1],obstacles[i+1]...)
}

且对于已经越过的点,若x或y小于当前坐标的障碍物一律可以剔除 例如下图

Inkedsave _1__LI.jpg
Inkedsave _1__LI.jpg
当我们位于红点时,绿点的障碍物是一定不会遇到的我们只需要对其剔除,可以大大缩减程序运行时间(当时在这里卡了好久

if obstacles[i][0]>x||obstacles[i][1]>y||(obstacles[i][0]==rx&&obstacles[i][1]<ry)||(obstacles[i][1]==ry&&obstacles[i][0]<rx)){
    obstacles=append(obstacles[i-1],obstacles[i+1]...)
}

完整代码

func robot(command string, obstacles [][]int, x int, y int) bool {
    rx,ry:=0,0
    
    for i:=0;i<len(command);i++{
        switch command[i]{
            case 'R':rx++;break;
            case 'U':ry++;break;
        }
        for i:=range obstacles{
            if rx==obstacles[i][0]&&ry==obstacles[i][1]{
                return false    //即撞毁
            }
            if obstacles[i][0]>x||obstacles[i][1]>y||(obstacles[i][0]==rx&&obstacles[i][1]<ry)||(obstacles[i][1]==ry&&obstacles[i][0]<rx)){
                obstacles=append(obstacles[i-1],obstacles[i+1]...)
            }
        }

        if rx==x&&ry==y{
            return true
        }
        if i==len(command)-1{
            i=-1
        }
    }
    return false
}

目前这道题思路改了,不再是设置海量的障碍物,而是将目的地数值设置巨大。