2022-02-22：机器人大冒险。 力扣团队买了一个可编程机器人，机器人初始位置在原点(0, 0)。小伙伴事先给机器人输入一串指令command，机器人就会无限循环这条指令的步骤进行移动。指令有两种： U: 向y轴正方向移动一格 R: 向x轴正方向移动一格。 不幸的是，在 xy 平面上还有一些障碍物，他们的坐标用obstacles表示。机器人一旦碰到障碍物就会被损毁。 给定终点坐标(x, y)，返回机器人能否完好地到达终点。如果能，返回true；否则返回false。

输入：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的长度 <= 1000 command由U，R构成，且至少有一个U，至少有一个R 0 <= x <= 1e9, 0 <= y <= 1e9 0 <= obstacles的长度 <= 1000 obstacles[i]不为原点或者终点

力扣LCP03。

答案2022-02-22：

具体见代码。

代码用golang编写。代码如下：

package main

import "fmt"

func main() {
    if true {
        command := "URR"
        obstacles := [][]int{}
        x := 3
        y := 2
        ret := robot1(command, obstacles, x, y)
        fmt.Println(ret)
    }
    if true {
        command := "URR"
        obstacles := [][]int{}
        x := 3
        y := 2
        ret := robot2(command, obstacles, x, y)
        fmt.Println(ret)
    }
}

func twoSelectOne(c bool, a, b int) int {
    if c {
        return a
    } else {
        return b
    }
}

func getMin(a, b int) int {
    if a < b {
        return a
    } else {
        return b
    }
}

func robot1(command string, obstacles [][]int, x, y int) bool {
    X := 0
    Y := 0
    //HashSet<Integer> set = new HashSet<>();
    set := make(map[int]struct{})
    //set.add(0);
    set[0] = struct{}{}
    for _, c := range []byte(command) {
        X += twoSelectOne(c == 'R', 1, 0)
        Y += twoSelectOne(c == 'U', 1, 0)
        set[(X<<10)|Y] = struct{}{}
    }
    // 不考虑任何额外的点，机器人能不能到达，(x，y)
    if !meet1(x, y, X, Y, set) {
        return false
    }
    for _, ob := range obstacles { // ob[0] ob[1]
        if ob[0] <= x && ob[1] <= y && meet1(ob[0], ob[1], X, Y, set) {
            return false
        }
    }
    return true
}

// 一轮以内，X，往右一共有几个单位
// Y, 往上一共有几个单位
// set, 一轮以内的所有可能性
// (x,y)要去的点
// 机器人从(0,0)位置，能不能走到(x,y)
func meet1(x, y, X, Y int, set map[int]struct{}) bool {
    if X == 0 { // Y != 0 往上肯定走了！
        return x == 0
    }
    if Y == 0 {
        return y == 0
    }
    // 至少几轮？
    atLeast := getMin(x/X, y/Y)
    // 经历过最少轮数后，x剩多少？
    rx := x - atLeast*X
    // 经历过最少轮数后，y剩多少？
    ry := y - atLeast*Y
    _, ok := set[(rx<<10)|ry]
    return ok
}

// 此处为一轮以内，x和y最大能移动的步数，对应的2的几次方
// 比如本题，x和y最大能移动1000步，就对应2的10次方
// 如果换一个数据量，x和y最大能移动5000步，就对应2的13次方
// 只需要根据数据量修改这一个变量，剩下的代码不需要调整
//public static final int bit = 10;
var bit = 10

// 如果，x和y最大能移动的步数，对应2的bit次方
// 那么一个坐标(x,y)，所有的可能性就是：(2 ^ bit) ^ 2 = 2 ^ (bit * 2)
// 也就是，(1 << (bit << 1))个状态，记为bits
//public static int bits = (1 << (bit << 1));
var bits = (1 << (bit << 1))

// 为了表示下bits个状态，需要几个整数？
// 32位只需要一个整数，所以bits个状态，需要bits / 32 个整数
// 即整型长度需要 : bits >> 5
//public static int[] set = new int[bits >> 5];
var set = make([]int, bits>>5)

func robot2(command string, obstacles [][]int, x, y int) bool {
    //Arrays.fill(set, 0);
    for i := 0; i < len(set); i++ {
        set[i] = 0
    }
    set[0] = 1
    X := 0
    Y := 0
    for _, c := range []byte(command) {
        X += twoSelectOne(c == 'R', 1, 0)
        Y += twoSelectOne(c == 'U', 1, 0)
        add((X << 10) | Y)
    }
    if !meet2(x, y, X, Y) {
        return false
    }
    for _, ob := range obstacles {
        if ob[0] <= x && ob[1] <= y && meet2(ob[0], ob[1], X, Y) {
            return false
        }
    }
    return true
}

func meet2(x, y, X, Y int) bool {
    if X == 0 {
        return x == 0
    }
    if Y == 0 {
        return y == 0
    }
    atLeast := getMin(x/X, y/Y)
    rx := x - atLeast*X
    ry := y - atLeast*Y
    return contains((rx << 10) | ry)
}

func add(status int) {
    set[status>>5] |= 1 << (status & 31)
}

func contains(status int) bool {
    return (status < bits) && (set[status>>5]&(1<<(status&31))) != 0
}

// int num -> 32位的状态
// 请打印这32位状态
func printBinary(num int) {
    for i := 31; i >= 0; i-- {
        //System.out.print((num & (1 << i)) != 0 ? "1" : "0");
        if (num & (1 << i)) != 0 {
            fmt.Print("1")
        } else {
            fmt.Print("0")
        }
    }
    //System.out.println();
    fmt.Println("")
}

执行结果如下： 图片

左神java代码