机器人大冒险。
力扣团队买了一个可编程机器人，机器人初始位置在原点(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]不为原点或者终点
具体见代码。
代码用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("")
}执行结果如下：
